Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

There are $N$ boxes on a table, numbered $1$ through $N$ from left to right. Each box has a number written on it; let's denote the number written on box $i$ by $A_{i}$.

Two players ― Jafar and Almir ― are playing a game that lasts for $K$ turns. The rules of the game are as follows:
Before the game starts, they flip a coin to decide the starting player.
In the first turn, the starting player chooses a box and places the ball in it.
Afterwards, the players alternate turns (in the second turn, the non-starting player is playing).
In each turn, the current player can move the ball one box to the left (unless it is in box $1$) or one box to the right (unless it is in box $N$).
The result of the game is the number written on the box containing the ball after $K$ turns.

Jafar plays in such a way that when the game ends, the number on the box which contains the ball is the biggest possible. On the contrary, Almir wants this number to be the smallest possible.

You know which player moves first. Determine the result of the game, assuming that both players play optimally.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains three space-separated integers $N$, $K$ and $P$, where $P$ denotes the starting player (Jafar if $P = 0$, Almir if $P = 1$).
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$,

------  Output ------
For each test case, print a single line containing one integer ― the result of the game.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$2 ≤ N ≤ 100$
$1 ≤ K ≤ 10^{9}$
$0 ≤ P ≤ 1$
$1 ≤ A_{i} ≤ 10^{9}$ for each valid $i$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
2

4 3 0

4 1 9 5

4 3 1

4 1 9 5
----- Sample Output 1 ------ 
9

1

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Data structures

Game theory


Solutions:
from sys import stdin
input = stdin.readline

def answer():
	if p == 0 and k & 1:
		return max(a)
	if p == 1 and k & 1:
		return min(a)
	(m1, m2) = (a[1], a[1])
	for i in range(1, n - 1):
		m1 = max(m1, min(a[i - 1], a[i + 1]))
		m2 = min(m2, max(a[i - 1], a[i + 1]))
	m1 = max(m1, a[n - 2])
	m2 = min(m2, a[n - 2])
	if p == 0:
		return m1
	else:
		return m2
for T in range(int(input())):
	(n, k, p) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


t = int(input())
for i in range(t):
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if p == 0:
		if (k - 1) % 2 == 0:
			print(max(l))
		else:
			ans = l[1]
			l.append(l[-2])
			for j in range(1, n):
				ans = max(ans, min(l[j - 1], l[j + 1]))
			print(ans)
	elif (k - 1) % 2 == 0:
		print(min(l))
	else:
		ans = l[1]
		l.append(l[-2])
		for j in range(1, n):
			ans = min(ans, max(l[j - 1], l[j + 1]))
		print(ans)


test = int(input())
for _ in range(test):
	(n, k, p) = map(int, input().split())
	li = list(map(int, input().split()))
	if p == 0:
		if (k - 1) % 2 == 0:
			print(max(li))
		else:
			ans = li[1]
			li.append(li[-2])
			for i in range(1, n):
				ans = max(ans, min(li[i - 1], li[i + 1]))
			print(ans)
	elif (k - 1) % 2 == 0:
		print(min(li))
	else:
		ans = li[1]
		li.append(li[-2])
		for i in range(1, n):
			ans = min(ans, max(li[i - 1], li[i + 1]))
		print(ans)


import sys
import math
from collections import defaultdict

def fout(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fin():
	return sys.stdin.readline().strip()
mod = pow(10, 9) + 7
t = int(fin())
while t > 0:
	t -= 1
	(n, k, p) = map(int, fin().split())
	a = [int(x) for x in fin().split()]
	if p == 0:
		if (k - 1) % 2 == 0:
			print(max(a))
		else:
			ans = a[1]
			a.append(a[-2])
			for i in range(1, n):
				ans = max(ans, min(a[i - 1], a[i + 1]))
			print(ans)
	elif (k - 1) % 2 == 0:
		print(min(a))
	else:
		ans = a[1]
		a.append(a[-2])
		for i in range(1, n):
			ans = min(ans, max(a[i - 1], a[i + 1]))
		print(ans)


for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if k % 2 == 1:
		print(max(l)) if p == 0 else print(min(l))
	elif p == 0:
		big = max(l[1], l[-2])
		for i in range(1, n - 1):
			if min(l[i - 1], l[i + 1]) > big:
				big = min(l[i - 1], l[i + 1])
		print(big)
	else:
		small = min(l[1], l[-2])
		for i in range(1, n - 1):
			if max(l[i - 1], l[i + 1]) < small:
				small = max(l[i - 1], l[i + 1])
		print(small)


t = int(input())
while t:
	(n, k, p) = map(int, input().split())
	A = list(map(int, input().split()))
	if p == 0:
		if k % 2 != 0:
			print(max(A))
		else:
			m = A[1]
			for i in range(1, n):
				if i == n - 1:
					m = max(m, A[n - 2])
				else:
					m = max(m, min(A[i - 1], A[i + 1]))
			print(m)
	elif k % 2 != 0:
		print(min(A))
	else:
		m = A[1]
		for i in range(1, n):
			if i == n - 1:
				m = min(m, A[n - 2])
			else:
				m = min(m, max(A[i - 1], A[i + 1]))
		print(m)
	t -= 1


for i in range(int(input())):
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if k % 2 == 1:
		if p == 0:
			print(max(l))
		else:
			print(min(l))
	elif p == 0:
		bada = max(l[1], l[-2])
		for i in range(1, n - 1):
			if min(l[i - 1], l[i + 1]) > bada:
				bada = min(l[i - 1], l[i + 1])
		print(bada)
	else:
		chota = min(l[1], l[-2])
		for i in range(1, n - 1):
			if max(l[i - 1], l[i + 1]) < chota:
				chota = max(l[i - 1], l[i + 1])
		print(chota)


t = int(input())
while t > 0:
	(n, k, p) = map(int, input().split())
	a = list(map(int, input().split()))
	overMax = max(a)
	overMin = min(a)
	ma = 0
	mi = 10000000000
	for i in range(n):
		if i == 0:
			ma = max(ma, a[i + 1])
			mi = min(mi, a[i + 1])
		elif i == n - 1:
			ma = max(ma, a[i - 1])
			mi = min(mi, a[i - 1])
		else:
			ma = max(ma, min(a[i + 1], a[i - 1]))
			mi = min(mi, max(a[i + 1], a[i - 1]))
	if k % 2 != 0:
		if p == 0:
			print(overMax)
		else:
			print(overMin)
	elif p == 0:
		print(ma)
	else:
		print(mi)
	t = t - 1


import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	t = I()
	l = []
	for _ in range(t):
		(n, k, p) = MI()
		a = LI()
		if k % 2 == 1:
			if p == 0:
				l.append(max(a))
			else:
				l.append(min(a))
		else:
			best = a[1]
			for i in range(1, n):
				if i == n - 1:
					if p == 0:
						best = max(best, a[n - 2])
					else:
						best = min(best, a[n - 2])
				elif p == 0:
					best = max(best, min(a[i - 1], a[i + 1]))
				else:
					best = min(best, max(a[i - 1], a[i + 1]))
			l.append(best)
	for i in range(t):
		pf(str(l[i]))
main()


t = int(input())
while t:
	t = t - 1
	(n, k, p) = map(int, input().split())
	arr = [int(n) for n in input().split()]
	if k % 2 != 0:
		if p == 0:
			print(max(arr))
		else:
			print(min(arr))
	elif p == 0:
		x = arr[1]
		if arr[n - 2] > x:
			x = arr[n - 2]
		for i in range(1, n - 1):
			x2 = arr[i - 1]
			if x2 > arr[i + 1]:
				x2 = arr[i + 1]
			if x2 > x:
				x = x2
		print(x)
	else:
		x = arr[1]
		if arr[n - 2] < x:
			x = arr[n - 2]
		for i in range(1, n - 1):
			x2 = arr[i - 1]
			if x2 < arr[i + 1]:
				x2 = arr[i + 1]
			if x2 < x:
				x = x2
		print(x)


def main():
	t = int(input())
	while t > 0:
		(n, k, p) = map(int, input().split())
		l = list(map(int, input().split()))
		if k % 2 != 0:
			if p == 0:
				print(max(l))
			else:
				print(min(l))
		elif p == 0:
			l.append(99999999999)
			l.insert(0, 99999999999)
			MAX = -99999999999
			for i in range(1, n + 1):
				MAX = max(MAX, min(l[i - 1], l[i + 1]))
			print(MAX)
		else:
			l.append(-99999999999)
			l.insert(0, -99999999999)
			MIN = 99999999999
			for i in range(1, n + 1):
				MIN = min(MIN, max(l[i - 1], l[i + 1]))
			print(MIN)
		t -= 1
main()


t = int(input())
for l in range(t):
	inp = list(map(int, input().split()))
	k = inp[1]
	p = inp[2]
	inp = list(map(int, input().split()))
	if k % 2 == 1:
		if p == 1:
			print(min(inp))
		if p == 0:
			print(max(inp))
	elif p == 1:
		k = 99999999999
		for i in range(1, len(inp) - 1):
			a = max(inp[i + 1], inp[i - 1])
			if a < k:
				k = a
		print(min(k, inp[1], inp[-2]))
	else:
		k = 0
		for i in range(1, len(inp) - 1):
			a = min(inp[i + 1], inp[i - 1])
			if a > k:
				k = a
		print(max(k, inp[1], inp[-2]))


from bisect import bisect_left

def b_search(a, x):
	i = bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1
from sys import stdin
t = int(stdin.readline())
while t:
	(n, k, p) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	(mx, mn) = (max(arr), min(arr))
	(xmx, xmn) = (b_search(arr, mx), b_search(arr, mn))
	if p == 0:
		if k & 1:
			print(mx)
		else:
			ans = 0
			for i in range(n):
				if i == 0:
					if arr[i + 1] > ans:
						ans = arr[i + 1]
				elif i == n - 1:
					if arr[i - 1] > ans:
						ans = arr[i - 1]
				else:
					ans = max(ans, min(arr[i + 1], arr[i - 1]))
			print(ans)
	elif k & 1:
		print(mn)
	else:
		ans = float('inf')
		for i in range(n):
			if i == 0:
				if arr[i + 1] < ans:
					ans = arr[i + 1]
			elif i == n - 1:
				if arr[i - 1] < ans:
					ans = arr[i - 1]
			else:
				ans = min(ans, max(arr[i + 1], arr[i - 1]))
		print(ans)
	t -= 1


for ti in range(int(input())):
	(n, k, p) = map(int, input().split())
	ays = list(map(int, input().split()))[:n]
	if k % 2 == 1:
		if p == 0:
			print(max(ays))
		else:
			print(min(ays))
	else:
		shu = ays[1:] + [ays[-2]]
		shd = [ays[1]] + ays[:n - 1]
		if p == 0:
			print(max((min(s) for s in zip(shu, shd))))
		else:
			print(min((max(s) for s in zip(shu, shd))))


t = int(input())
for test1 in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	k = inp[1]
	p = inp[2]
	a = list(map(int, input().split()))
	ans = -1
	if p == 0:
		if k % 2 == 1:
			mx = a[0]
			for i in range(1, n):
				if a[i] > mx:
					mx = a[i]
			ans = mx
		else:
			p = [0 for i in range(n)]
			p[0] = a[1]
			p[n - 1] = a[n - 2]
			for i in range(1, n - 1):
				prev = a[i - 1]
				nex = a[i + 1]
				p[i] = nex
				if prev < nex:
					p[i] = prev
			ans = p[0]
			for i in range(1, n):
				if p[i] > ans:
					ans = p[i]
	elif k % 2 == 1:
		mn = a[0]
		for i in range(1, n):
			if a[i] < mn:
				mn = a[i]
		ans = mn
	else:
		p = [0 for i in range(n)]
		p[0] = a[1]
		p[n - 1] = a[n - 2]
		for i in range(1, n - 1):
			prev = a[i - 1]
			nex = a[i + 1]
			p[i] = nex
			if prev > nex:
				p[i] = prev
		ans = p[0]
		for i in range(1, n):
			if p[i] < ans:
				ans = p[i]
	print(ans)


for _ in range(int(input())):
	(a, b, c) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	if b % 2 != 0 or a == 2:
		if c:
			print(min(l))
		else:
			print(max(l))
	elif c:
		mi = 100000000000
		mi = l[1]
		for i in range(1, a - 1):
			v = max(l[i - 1], l[i + 1])
			if mi > v:
				mi = v
		if mi > l[-2]:
			mi = l[-2]
		print(mi)
	else:
		mi = l[1]
		for i in range(1, a - 1):
			v = min(l[i - 1], l[i + 1])
			if mi < v:
				mi = v
		if mi < l[-2]:
			mi = l[-2]
		print(mi)


def main():
	t = int(input())
	while t > 0:
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		p = l[2]
		a = list(map(int, input().split()))
		if k % 2 != 0:
			print(max(a) if p == 0 else min(a))
		elif p == 0:
			ans = 0
			for i in range(0, n):
				ans1 = min(a[i - 1], a[i + 1]) if i != 0 and i != n - 1 else a[1] if i == 0 else a[n - 2]
				if ans1 > ans:
					ans = ans1
			print(ans)
		else:
			ans = max(a)
			for i in range(0, n):
				ans1 = max(a[i - 1], a[i + 1]) if i != 0 and i != n - 1 else a[1] if i == 0 else a[n - 2]
				if ans1 < ans:
					ans = ans1
			print(ans)
		t -= 1
main()


for T in range(int(input())):
	(n, k, p) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	(val, ans) = (0, 0)
	if p == 0:
		if k & 1:
			print(max(a))
		else:
			ans = 0
			for i in range(1, n - 1):
				ans = max(ans, min(a[i - 1], a[i + 1]))
			print(max(ans, a[1], a[-2]))
	elif p == 1:
		if k & 1:
			print(min(a))
			continue
		else:
			ans = 10 ** 11
			for i in range(1, n - 1):
				ans = min(ans, max(a[i - 1], a[i + 1]))
			print(min(ans, a[1], a[-2]))


for a0 in range(int(input())):
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if k % 2 != 0:
		if p:
			print(min(l))
		else:
			print(max(l))
	elif p:
		l1 = min(l[1], l[-2])
		for i in range(1, n - 1):
			if l1 > max(l[i + 1], l[i - 1]):
				l1 = max(l[i + 1], l[i - 1])
		print(l1)
	else:
		l1 = max(l[1], l[-2])
		for i in range(1, n - 1):
			if l1 < min(l[i + 1], l[i - 1]):
				l1 = min(l[i + 1], l[i - 1])
		print(l1)


for _ in range(int(input())):
	(n, k, p) = (int(x) for x in input().split())
	s = [int(x) for x in input().split()]
	if k % 2 == 1:
		if p == 0:
			print(max(s))
		else:
			print(min(s))
	elif p == 1:
		max_pair_val = min(s[1], s[-2])
		for i in range(n - 2):
			max_pair_val = min(max_pair_val, max(s[i], s[i + 2]))
		print(max_pair_val)
	else:
		min_pair_val = max(s[1], s[-2])
		for i in range(n - 2):
			min_pair_val = max(min_pair_val, min(s[i], s[i + 2]))
		print(min_pair_val)


def main(debug=False):
	for _ in range(int(input())):
		(n, k, p) = map(int, input().split())
		a = list(map(int, input().split()))
		if k % 2 == 1:
			if p == 0:
				print(max(a))
			else:
				print(min(a))
		else:
			ans = -1
			if p == 0:
				ans = max(a[1], a[n - 2])
				for j in range(1, n - 1):
					ans = max(ans, min(a[j - 1], a[j + 1]))
			else:
				ans = min(a[1], a[n - 2])
				for j in range(1, n - 1):
					ans = min(ans, max(a[j - 1], a[j + 1]))
			print(ans)
while True:
	try:
		main(debug=False)
	except (ValueError, EOFError) as e:
		break


for _ in range(int(input())):
	(n, k, s) = map(int, input().split())
	a = [int(i) for i in input().split()]
	if k % 2 != 0:
		if s == 0:
			print(max(a))
		else:
			print(min(a))
	elif s == 1:
		temp = min(a[1], a[n - 2])
		for i in range(1, n - 1):
			temp = min(temp, max(a[i + 1], a[i - 1]))
		print(temp)
	else:
		temp = max(a[1], a[n - 2])
		for i in range(1, n - 1):
			temp = max(temp, min(a[i + 1], a[i - 1]))
		print(temp)


from sys import stdin
t = int(stdin.readline())
while t:
	(n, k, p) = [int(x) for x in stdin.readline().split()]
	a = [int(x) for x in stdin.readline().split()]
	if p == 0:
		if k % 2 != 0:
			print(max(a))
		else:
			max_jaf = a[1]
			for i in range(1, n - 1):
				if max_jaf < min(a[i - 1], a[i + 1]):
					max_jaf = min(a[i - 1], a[i + 1])
			print(max(max_jaf, a[1], a[-2]))
	elif k % 2 != 0:
		print(min(a))
	else:
		max_jaf = a[1]
		for i in range(1, n - 1):
			if max_jaf > max(a[i - 1], a[i + 1]):
				max_jaf = max(a[i - 1], a[i + 1])
		print(min(max_jaf, a[1], a[-2]))
	t -= 1


number_of_test_cases = int(input())
while number_of_test_cases != 0:
	(n, k, p) = input().split()
	(n, k, p) = [int(n), int(k), int(p)]
	lis = []
	(temp, ind, c) = (0, 0, 0)
	lis = [int(j) for j in input().split()]
	if k % 2 == 0:
		if p == 1:
			temp = min(lis[1], lis[n - 2])
			for i in range(1, n - 1):
				if temp > max(lis[i + 1], lis[i - 1]):
					temp = max(lis[i + 1], lis[i - 1])
			print(temp)
		else:
			temp = max(lis[1], lis[n - 2])
			for i in range(1, n - 1):
				if temp < min(lis[i + 1], lis[i - 1]):
					temp = min(lis[i + 1], lis[i - 1])
			print(temp)
	elif p == 1:
		print(min(lis))
	else:
		print(max(lis))
	number_of_test_cases -= 1


T = int(input())
for j in range(T):
	(n, k, p) = input().split()
	n = int(n)
	k = int(k)
	li = input().split()
	for i in range(n):
		li[i] = int(li[i])
	if p == '0':
		li1 = []
		for i in range(n):
			if i == 0:
				li1.append(li[i + 1])
			elif i == n - 1:
				li1.append(li[i - 1])
			else:
				li1.append(min(li[i + 1], li[i - 1]))
		if k % 2 == 1:
			print(max(li))
		else:
			print(max(li1))
	else:
		li1 = []
		for i in range(n):
			if i == 0:
				li1.append(li[i + 1])
			elif i == n - 1:
				li1.append(li[i - 1])
			else:
				li1.append(max(li[i + 1], li[i - 1]))
		if k % 2 == 1:
			print(min(li))
		else:
			print(min(li1))


def max_box_game(n, k, ls):
	if k % 2 == 1:
		return max(ls)
	elif n > 2:
		minval = max(ls[1], ls[-2])
		for i in range(1, n - 1):
			temp = min(ls[i - 1], ls[i + 1])
			if temp > minval:
				minval = temp
		return minval
	elif ls[0] > ls[1]:
		return ls[0]
	else:
		return ls[1]

def min_box_game(n, k, ls):
	if k % 2 == 1:
		return min(ls)
	elif n > 2:
		maxval = min(ls[1], ls[-2])
		for i in range(1, n - 1):
			temp = max(ls[i - 1], ls[i + 1])
			if temp < maxval:
				maxval = temp
		return maxval
	elif ls[0] < ls[1]:
		return ls[0]
	else:
		return ls[1]
t = int(input().strip())
while t > 0:
	t -= 1
	(n, k, p) = list(map(int, input().strip().split()))
	ls = list(map(int, input().strip().split()))
	if p == 0:
		print(max_box_game(n, k, ls))
	else:
		print(min_box_game(n, k, ls))


t = int(input())
while t > 0:
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	ma = max(l)
	mi = min(l)
	(i1, i2) = (-1, -1)
	for i in range(n):
		if l[i] == ma:
			i1 = i
		if l[i] == mi:
			i2 = i
	if p == 0:
		if k % 2 != 0:
			print(ma)
		else:
			a = max(l[1], l[n - 2])
			for i in range(1, n - 1):
				a = max(min(l[i - 1], l[i + 1]), a)
			print(a)
	elif k % 2 != 0:
		print(mi)
	else:
		a = min(l[1], l[n - 2])
		for i in range(1, n - 1):
			a = min(max(l[i - 1], l[i + 1]), a)
		print(a)
	t -= 1


for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if m % 2 != 0:
		if k == 0:
			print(max(l))
		else:
			print(min(l))
	else:
		if k == 1:
			ans = min(l[1], l[-2])
			for i in range(1, n - 1):
				ans = min(ans, max(l[i - 1], l[i + 1]))
		else:
			ans = max(l[1], l[-2])
			for i in range(1, n - 1):
				ans = max(ans, min(l[i - 1], l[i + 1]))
		print(ans)


import numpy as np
for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	a = [int(i) for i in input().split()]
	if k & 1 and p == 0:
		print(max(a))
	elif k & 1 and p == 1:
		print(min(a))
	elif p != 1:
		ans = max(a[1], a[n - 2])
		for i in range(1, n - 1):
			ans = max(ans, min(a[i - 1], a[i + 1]))
		print(ans)
	else:
		ans = min(a[1], a[n - 2])
		for i in range(1, n - 1):
			ans = min(ans, max(a[i - 1], a[i + 1]))
		print(ans)


t = int(input())
while t:
	t -= 1
	(n, k, p) = map(int, input().strip().split())
	l = list(map(int, input().strip().split()))
	a = max(l)
	b = min(l)
	if a == b:
		print(a)
		continue
	x = l.index(a)
	y = l.index(b)
	c = x - y
	if p == 0:
		if k % 2 == 1:
			print(a)
		else:
			v = []
			v.append(l[1])
			v.append(l[n - 2])
			for i in range(1, n - 1):
				v.append(min(l[i - 1], l[i + 1]))
			print(max(v))
	elif k % 2 == 1:
		print(b)
	else:
		v = []
		v.append(l[1])
		v.append(l[n - 2])
		for i in range(1, n - 1):
			v.append(max(l[i - 1], l[i + 1]))
		print(min(v))


t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	a = list(map(int, input().split()))
	if k % 2 == 1:
		if p == 0:
			print(max(a))
		else:
			print(min(a))
	elif p == 0:
		maxx = -1
		for i in range(1, n - 1):
			if a[i - 1] <= a[i + 1] and a[i - 1] > maxx:
				maxx = a[i - 1]
			elif a[i + 1] < a[i - 1] and a[i + 1] > maxx:
				maxx = a[i + 1]
		if a[1] > maxx:
			maxx = a[1]
		if a[n - 2] > maxx:
			maxx = a[n - 2]
		print(maxx)
	else:
		minn = max(a) + 1
		for i in range(1, n - 1):
			if a[i - 1] >= a[i + 1] and a[i - 1] < minn:
				minn = a[i - 1]
			elif a[i + 1] > a[i - 1] and a[i + 1] < minn:
				minn = a[i + 1]
		if a[1] < minn:
			minn = a[1]
		if a[n - 2] < minn:
			minn = a[n - 2]
		print(minn)


t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	c = []
	if p == 0:
		if k % 2 == 1:
			print(max(a))
		else:
			for i in range(1, n - 1):
				b.append(min(a[i - 1], a[i + 1]))
			b.append(a[1])
			b.append(a[n - 2])
			print(max(b))
	elif k % 2 == 1:
		print(min(a))
	else:
		for i in range(1, n - 1):
			c.append(max(a[i - 1], a[i + 1]))
		c.append(a[1])
		c.append(a[n - 2])
		print(min(c))


def min_possible(A, n):
	B = [n]
	B.extend(A)
	B.append(n)
	answer = []
	for i in range(1, len(A) + 1):
		answer.append(min(B[i - 1], B[i + 1]))
	return answer

def max_possible(A, n):
	B = [n]
	B.extend(A)
	B.append(n)
	answer = []
	for i in range(1, len(A) + 1):
		answer.append(max(B[i - 1], B[i + 1]))
	return answer

def play_game(box, n, k, p):
	M = max(box)
	m = min(box)
	if k % 2 == 1:
		if p == 0:
			return M
		if p == 1:
			return m
	elif p == 0:
		List = min_possible(box, M)
		return max(List)
	else:
		List = max_possible(box, m)
		return min(List)
t = int(input())
for i in range(t):
	(n, k, p) = [int(x) for x in input().split()]
	box = [int(x) for x in input().split()]
	answer = play_game(box, n, k, p)
	print(answer)


t = int(input())
while t > 0:
	(n, k, p) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	if p == 0:
		if k % 2 == 0:
			mini = min(arr)
			for i in range(n):
				if i != 0 and i != n - 1:
					m = min(arr[i - 1], arr[i + 1])
				elif i != 0:
					m = arr[i - 1]
				elif i != n - 1:
					m = arr[i + 1]
				if m > mini:
					mini = m
			print(mini)
		else:
			print(max(arr))
	elif k % 2 == 0:
		maxi = max(arr)
		for i in range(n):
			if i != 0 and i != n - 1:
				m = max(arr[i - 1], arr[i + 1])
			elif i != 0:
				m = arr[i - 1]
			elif i != n - 1:
				m = arr[i + 1]
			if m < maxi:
				maxi = m
		print(maxi)
	else:
		print(min(arr))
	t = t - 1


for _ in range(int(input())):
	(n, k, p) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if k % 2 != 0:
		if p == 0:
			print(max(a))
		else:
			print(min(a))
	else:
		mx = max(a[1], a[-2])
		mn = min(a[1], a[-2])
		if p == 0:
			for i in range(1, n - 1):
				mx = max(mx, min(a[i - 1], a[i + 1]))
			print(mx)
		else:
			for i in range(1, n - 1):
				mn = min(mn, max(a[i - 1], a[i + 1]))
			print(mn)


for t in range(int(input())):
	(n, k, p) = [int(j) for j in input().split()]
	a = [int(j) for j in input().split()]
	if k % 2 == 1:
		if p == 1:
			print(min(a))
		else:
			print(max(a))
	else:
		if p == 1:
			ans = min(a[1], a[n - 2])
			for i in range(1, n - 1):
				tans = max(a[i - 1], a[i + 1])
				ans = min(tans, ans)
		else:
			ans = max(a[1], a[n - 2])
			for i in range(1, n - 1):
				tans = min(a[i + 1], a[i - 1])
				ans = max(tans, ans)
		print(ans)


t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	a = list(map(int, input().split()))
	a1 = max(a)
	a2 = min(a)
	if k % 2 == 1:
		if p == 0:
			print(a1)
		else:
			print(a2)
	else:
		for i in range(n):
			if i == 0:
				temp1 = a[i + 1]
				a3 = temp1
				a4 = temp1
			elif i == n - 1:
				temp1 = a[i - 1]
				if temp1 > a3:
					a3 = temp1
				if temp1 < a4:
					a4 = temp1
			else:
				temp1 = min(a[i - 1], a[i + 1])
				temp2 = max(a[i - 1], a[i + 1])
				if temp1 > a3:
					a3 = temp1
				if temp2 < a4:
					a4 = temp2
		if p == 0:
			print(a3)
		else:
			print(a4)


tc = int(input())
for _ in range(tc):
	(n, k, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	sml = arr.index(min(arr))
	big = arr.index(max(arr))
	if k % 2 != 0:
		if not p:
			print(arr[big])
		else:
			print(arr[sml])
	elif not p:
		choice1 = max(arr[1], arr[-2])
		for i in range(1, n - 1):
			choice1 = max(choice1, min(arr[i - 1], arr[i + 1]))
		print(choice1)
	else:
		choice2 = min(arr[1], arr[-2])
		for i in range(1, n - 1):
			choice2 = min(choice2, max(arr[i - 1], arr[i + 1]))
		print(choice2)


def maxarr(lst):
	m = []
	for i in range(1, len(lst) - 1):
		m.append(min(lst[i - 1], lst[i + 1]))
	m.append(lst[1])
	m.append(lst[len(lst) - 2])
	return max(m)

def minarr(lst):
	m = []
	for i in range(1, len(lst) - 1):
		m.append(max(lst[i - 1], lst[i + 1]))
	m.append(lst[1])
	m.append(lst[len(lst) - 2])
	return min(m)
for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	num = list(map(int, input().split()))
	if k % 2 != 0:
		if p == 0:
			print(max(num))
		else:
			print(min(num))
	else:
		if p == 0:
			result = maxarr(num)
		else:
			result = minarr(num)
		print(result)


t = int(input())
while t > 0:
	t -= 1
	(n, k, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	if p == 0:
		if k % 2 == 0:
			ans = 0
			for i in range(n):
				if i == 0:
					ans = max(ans, arr[i + 1])
				elif i == n - 1:
					ans = max(ans, arr[i - 1])
				else:
					ans = max(min(arr[i - 1], arr[i + 1]), ans)
			print(ans)
		else:
			print(max(arr))
	elif p == 1:
		if k % 2 == 0:
			ans = 1e+18
			for i in range(n):
				if i == 0:
					ans = min(ans, arr[i + 1])
				elif i == n - 1:
					ans = min(ans, arr[i - 1])
				else:
					ans = min(max(arr[i - 1], arr[i + 1]), ans)
			print(ans)
		else:
			print(min(arr))


T = int(input())
for t in range(T):
	(N, k, p) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	if k % 2 == 1:
		if p == 0:
			ans = -1
			for i in range(N):
				if a[i] > ans:
					ans = a[i]
		else:
			ans = 10000000000
			for i in range(N):
				if a[i] < ans:
					ans = a[i]
		print(ans)
	else:
		if p == 0:
			ans = -1
			for i in range(1, N - 1):
				ans = max(ans, min(a[i - 1], a[i + 1]))
			ans = max(ans, a[1])
			ans = max(ans, a[-2])
		else:
			ans = 10000000000
			for i in range(1, N - 1):
				ans = min(ans, max(a[i - 1], a[i + 1]))
			ans = min(ans, a[1])
			ans = min(ans, a[-2])
		print(ans)


t = int(input())
for i in range(t):
	lis = input()
	lis = lis.split()
	n = int(lis[0])
	k = int(lis[1])
	p = int(lis[2])
	lis = input()
	lis = lis.split()
	for m in range(n):
		lis[m] = int(lis[m])
	if k % 2 != 0:
		if p == 0:
			print(max(lis))
		else:
			print(min(lis))
	else:
		max222 = lis[1]
		min222 = lis[1]
		if n == 1:
			print(lis[0])
		else:
			for mm in range(1, n - 1):
				if lis[mm - 1] < lis[mm + 1]:
					max1 = lis[mm - 1]
				else:
					max1 = lis[mm + 1]
				if lis[mm - 1] > lis[mm + 1]:
					min1 = lis[mm - 1]
				else:
					min1 = lis[mm + 1]
				if min222 > min1:
					min222 = min1
				if max222 < max1:
					max222 = max1
			if lis[n - 2] > max222:
				max222 = lis[n - 2]
			if lis[n - 2] < min222:
				min222 = lis[n - 2]
			if p == 0:
				print(max222)
			else:
				print(min222)


for _ in range(int(input())):
	(a, b, c) = map(int, input().split())
	lst = list(map(int, input().split()))
	if c:
		mn = min(lst)
		if b % 2 == 1:
			print(mn)
		else:
			ans = []
			temp = [0] + lst + [0]
			for i in range(1, a + 1):
				ans.append(max(temp[i - 1], temp[i + 1]))
			print(min(ans))
	else:
		mx = max(lst)
		if b % 2 == 1:
			print(mx)
		else:
			ans = []
			temp = [int(10000000000.0 + 1)] + lst + [int(10000000000.0 + 1)]
			for i in range(1, a + 1):
				ans.append(min(temp[i - 1], temp[i + 1]))
			print(max(ans))


t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	if p == 0:
		if k % 2 != 0:
			print(max(arr))
		else:
			l = max(arr[1], arr[-2])
			for i in range(1, n - 1):
				if l < min(arr[i - 1], arr[i + 1]):
					l = min(arr[i - 1], arr[i + 1])
			print(l)
	elif k % 2 != 0:
		print(min(arr))
	else:
		l = min(arr[1], arr[-2])
		for i in range(1, n - 1):
			if l > max(arr[i - 1], arr[i + 1]):
				l = max(arr[i - 1], arr[i + 1])
		print(l)


for _ in range(int(input())):
	(n, k, p) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if p == 0 and k % 2 != 0:
		print(max(arr))
	elif p == 1 and k % 2 != 0:
		print(min(arr))
	elif p == 0 and k % 2 == 0:
		ans = []
		ans.append(arr[1])
		ans.append(arr[n - 2])
		for i in range(1, n - 1):
			ans.append(min(arr[i - 1], arr[i + 1]))
		print(max(ans))
	elif p == 1 and k % 2 == 0:
		ans = []
		ans.append(arr[1])
		ans.append(arr[n - 2])
		for i in range(1, n - 1):
			ans.append(max(arr[i - 1], arr[i + 1]))
		print(min(ans))


t = int(input())
for i in range(t):
	(n, k, p) = map(int, input().split())
	a = [int(x) for x in input().split()]
	if p == 0 and k % 2 == 1:
		print(max(a))
	elif p == 1 and k % 2 == 1:
		print(min(a))
	elif p == 0 and k % 2 == 0:
		temp = [0] * n
		temp[0] = a[1]
		temp[n - 1] = a[n - 2]
		for i in range(1, n - 1):
			temp[i] = min(a[i - 1], a[i + 1])
		print(max(temp))
	else:
		temp = [0] * n
		temp[0] = a[1]
		temp[n - 1] = a[n - 2]
		for i in range(1, n - 1):
			temp[i] = max(a[i - 1], a[i + 1])
		print(min(temp))


def compare(a, b, P):
	if P:
		return a if a < b else b
	return a if a > b else b

def solver():
	(N, K, P) = [int(x) for x in input().split()]
	P = bool(P)
	A = [int(x) for x in input().split()]
	target = min(A) if P else max(A)
	if A[1] == target or A[-2] == target:
		return target
	if K % 2 == 1:
		return target
	val = compare(A[1], A[-2], P)
	for i in range(1, len(A) - 1):
		comp = compare(A[i - 1], A[i + 1], not P)
		val = compare(val, comp, P)
	return val
for _ in range(int(input())):
	print(solver())


t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split(' '))
	a = [int(x) for x in input().split()]
	b = [a[1]] + [x for x in a] + [a[-2]]
	if p == 0:
		ans = 0
	else:
		ans = 10 ** 9 + 1
	if k % 2 == 0:
		odd = False
		even = True
	else:
		odd = True
		even = False
	if p == 0 and even:
		for j in range(1, n + 1):
			ans = max(ans, min(b[j - 1], b[j + 1]))
	elif p == 0 and odd:
		ans = max(a)
	elif p == 1 and odd:
		ans = min(a)
	else:
		for j in range(1, n + 1):
			ans = min(ans, max(b[j - 1], b[j + 1]))
	print(ans)


t = int(input())
while t:
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	mxx = l[0]
	mii = l[0]
	if n == 2:
		if p == 0:
			print(max(l))
		else:
			print(min(l))
	else:
		mx = max(l[1], l[n - 2])
		mi = min(l[1], l[n - 2])
		for i in range(1, n - 1):
			if min(l[i - 1], l[i + 1]) > mx:
				mx = min(l[i - 1], l[i + 1])
			if max(l[i - 1], l[i + 1]) < mi:
				mi = max(l[i - 1], l[i + 1])
			if l[i] > mxx:
				mxx = l[i]
			if mii > l[i]:
				mii = l[i]
		if l[n - 1] > mxx:
			mxx = l[n - 1]
		if mii > l[n - 1]:
			mii = l[n - 1]
		if k % 2 == 1:
			if p == 0:
				print(mxx)
			else:
				print(mii)
		elif p == 0:
			print(mx)
		else:
			print(mi)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if k & 1 == 1 and p == 0:
		print(max(l))
		continue
	elif k & 1 == 1 and p == 1:
		print(min(l))
		continue
	elif p == 1:
		for i in range(0, n):
			if i == n - 1:
				ans = min(ans, l[i - 1])
			elif i == 0:
				ans = l[1]
			else:
				ans = min(ans, max(l[i + 1], l[i - 1]))
	else:
		for i in range(0, n):
			if i == n - 1:
				ans = max(ans, l[i - 1])
			elif i == 0:
				ans = l[1]
			else:
				ans = max(ans, min(l[i + 1], l[i - 1]))
	print(ans)


for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	a = list(map(int, input().split()))
	if k % 2 == 1:
		if p == 0:
			print(max(a))
		if p == 1:
			print(min(a))
	if k % 2 == 0:
		if p == 0:
			a.append(float('inf'))
			m = -1
			for i in range(n):
				m = max(m, min(a[i - 1], a[i + 1]))
			print(m)
		if p == 1:
			a.append(-1)
			m = float('inf')
			for i in range(n):
				m = min(m, max(a[i - 1], a[i + 1]))
			print(m)


import sys
from heapq import heappop
from heapq import heappush
from heapq import heapify
from bisect import insort
from bisect import bisect_right
from bisect import bisect_left
from sys import stdin, stdout
from collections import defaultdict, deque
from math import log2, ceil, floor
inp = lambda : int(input())
sip = lambda : input()
mulip = lambda : map(int, input().split())
lst = lambda : list(map(int, input().split()))
slst = lambda : list(sip())
arr2d = lambda x: [[int(j) for j in input().split()] for i in range(x)]
odds = lambda l: len(list(filter(lambda x: x % 2 != 0, l)))
evens = lambda l: len(list(filter(lambda x: x % 2 == 0, l)))
mod = pow(10, 9) + 7
for _ in range(inp()):
	(n, k, p) = mulip()
	A = lst()
	if k % 2 == 1:
		if p == 0:
			print(max(A))
		elif p == 1:
			print(min(A))
	elif n == 2:
		if p == 0:
			print(max(A))
		elif p == 1:
			print(min(A))
	else:
		(mx, mn) = (0, pow(10, 9) + 1)
		for i in range(1, n - 1):
			mx = max(min(A[i - 1], A[i + 1]), mx)
			mn = min(max(A[i - 1], A[i + 1]), mn)
		mx = max(mx, A[1])
		mx = max(mx, A[n - 2])
		mn = min(mn, A[1])
		mn = min(mn, A[n - 2])
		if p == 1:
			print(mn)
		else:
			print(mx)


for t in range(int(input())):
	(n, k, p) = list(map(int, input().split(' ')))
	A = list(map(int, input().split(' ')))
	if k % 2:
		if p == 0:
			print(max(A))
		else:
			print(min(A))
	else:
		if p == 0:
			out = 0
			neigh = max(A[1], A[-2])
			for i in range(1, n - 1):
				if min(A[i - 1], A[i + 1]) > neigh:
					neigh = min(A[i - 1], A[i + 1])
					out = i
		else:
			out = 0
			neigh = min(A[1], A[-2])
			for i in range(1, n - 1):
				if max(A[i - 1], A[i + 1]) < neigh:
					neigh = max(A[i - 1], A[i + 1])
					out = i
		print(neigh)


def maxi(A, n):
	m = 0
	for i in range(n - 2):
		a = min(A[i], A[i + 2])
		if a > m:
			m = a
	if A[1] > m:
		m = A[1]
	if A[-2] > m:
		m = A[-2]
	return m

def mini(A, n):
	m = 10 ** 9
	for i in range(n - 2):
		a = max(A[i], A[i + 2])
		if a < m:
			m = a
	if A[1] < m:
		m = A[1]
	if A[-2] < m:
		m = A[-2]
	return m
t = int(input())
for i in range(t):
	(n, k, p) = map(int, input().split())
	A = [int(j) for j in input().split()]
	if k % 2 != 0:
		if p == 0:
			print(max(A))
		else:
			print(min(A))
	elif p == 0:
		print(maxi(A, n))
	else:
		print(mini(A, n))


for _ in range(int(input())):
	(n, k, p) = map(int, input().split())
	x = [int(n) for n in input().split()]
	mini = min(x)
	maxi = max(x)
	if k & 1:
		if p & 1:
			print(mini)
		else:
			print(maxi)
	else:
		if not p & 1:
			t = max(x[1], x[-2])
			for i in range(1, n - 1):
				e = min(x[i - 1], x[i + 1])
				t = max(e, t)
		else:
			t = min(x[1], x[-2])
			for i in range(1, n - 1):
				e = max(x[i - 1], x[i + 1])
				t = min(e, t)
		print(t)


import sys
t = int(input())
while t:
	(n, k, p) = map(int, input().split())
	a = [int(_) for _ in input().split()]
	if k % 2 != 0:
		if p == 0:
			print(max(a))
		else:
			print(min(a))
	elif p == 0:
		mx = max(a[1], a[n - 2])
		for i in range(1, n - 1):
			mx = max(mx, min(a[i - 1], a[i + 1]))
		print(mx)
	else:
		mn = min(a[1], a[n - 2])
		for i in range(1, n - 1):
			mn = min(mn, max(a[i - 1], a[i + 1]))
		print(mn)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k, p) = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	minIndices = []
	maxIndices = []
	greatest = max(a)
	least = min(a)
	for i in range(n):
		if a[i] == greatest:
			maxIndices.append(i)
	for i in range(n):
		if a[i] == least:
			minIndices.append(i)
	if k % 2:
		if p == 0:
			print(greatest)
		else:
			print(least)
	elif p == 0:
		if 1 in maxIndices or n - 2 in maxIndices:
			print(greatest)
		else:
			ans = []
			ans.append(a[1])
			ans.append(a[n - 2])
			for i in range(1, n - 1):
				ans.append(min(a[i - 1], a[i + 1]))
			print(max(ans))
	elif 1 in minIndices or n - 2 in minIndices:
		print(least)
	else:
		ans = []
		ans.append(a[1])
		ans.append(a[n - 2])
		for i in range(1, n - 1):
			ans.append(max(a[i - 1], a[i + 1]))
		print(min(ans))


t = int(input())
for z in range(t):
	count = 0
	wasim = 0
	jafar = 0
	sachin = 1
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if k % 2 != 0:
		count += 1
		if p == 0:
			wasim = sachin + jafar
			print(max(l))
		else:
			print(min(l))
	else:
		mx = 0
		mn = int(1000000000.0) + 5
		for i in range(n - 2):
			a = i
			b = i + 2
			for j in range(a, b + 1):
				mx = max(mx, min(l[a], l[b]))
				mn = min(mn, max(l[a], l[b]))
		if p == 0:
			print(max(mx, l[1], l[-2]))
		else:
			print(min(mn, l[1], l[-2]))


def side(i):
	res = []
	if i > 0:
		res.append(a[i - 1])
	if i < n - 1:
		res.append(a[i + 1])
	return res
t = int(input())
for _ in range(t):
	(n, k, p) = map(int, input().split())
	a = [int(i) for i in input().split()]
	mn = min(a)
	mx = max(a)
	if k & 1 and p == 0:
		print(mx)
	elif k & 1 and p == 1:
		print(mn)
	elif not k & 1 and p == 0:
		res = 0
		for i in range(n):
			ops = side(i)
			pick = min(ops)
			res = max(res, pick)
		print(res)
	elif not k & 1 and p == 1:
		res = float('inf')
		for i in range(n):
			ops = side(i)
			pick = max(ops)
			res = min(res, pick)
		print(res)


t = int(input())
for q in range(t):
	(n, k, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	if p == 0 and k & 1 == 1:
		print(max(arr))
	elif p == 1 and k & 1 == 1:
		print(min(arr))
	elif p == 0 and k & 1 == 0:
		arr2 = []
		if n == 2:
			print(max(arr))
			continue
		else:
			for i in range(n - 2):
				arr2.append(min(arr[i], arr[i + 2]))
			arr2 = sorted(arr2)
			print(max(arr2[-1], arr[n - 2], arr[1]))
	else:
		arr2 = []
		if n == 2:
			print(min(arr))
			continue
		else:
			for i in range(n - 2):
				arr2.append(max(arr[i], arr[i + 2]))
			arr2 = sorted(arr2)
			print(min(arr2[0], arr[n - 2], arr[1]))


t = int(input())
for z in range(t):
	(n, k, p) = map(int, input().split())
	l = list(map(int, input().split()))
	if k % 2 != 0:
		if p == 0:
			print(max(l))
		else:
			print(min(l))
	else:
		(a, b) = (l[1], l[-2])
		if p == 0 and max(l) == max(a, b):
			print(max(l))
		elif p == 1 and min(l) == min(a, b):
			print(min(l))
		else:
			mx = 0
			mn = int(1000000000.0) + 5
			for i in range(n - 2):
				a = i
				b = i + 2
				for j in range(a, b + 1):
					mx = max(mx, min(l[a], l[b]))
					mn = min(mn, max(l[a], l[b]))
			if p == 0:
				print(max(mx, l[1], l[-2]))
			else:
				print(min(mn, l[1], l[-2]))


t = int(input())
n = 0
k = 0
p = 0
for tc in range(t):
	(n, k, p) = list(map(int, input().split()))
	ar = list(map(int, input().split()))
	if k % 2 == 0:
		if p == 0:
			mx = [0 for i in range(n)]
			for i in range(n):
				tmpmx = -1
				if i == 0:
					mx[i] = ar[i + 1]
				elif i > 0 and i < n - 1:
					mx[i] = min(ar[i - 1], ar[i + 1])
				else:
					mx[i] = ar[i - 1]
			print(max(mx))
		else:
			mi = [0 for i in range(n)]
			for i in range(n):
				tmpmi = -1
				if i == 0:
					mi[i] = ar[i + 1]
				elif i > 0 and i < n - 1:
					mi[i] = max(ar[i - 1], ar[i + 1])
				else:
					mi[i] = ar[i - 1]
			print(min(mi))
	elif p == 0:
		print(max(ar))
	else:
		print(min(ar))


def main():
	t = int(input())
	while t > 0:
		t -= 1
		(n, k, p) = map(int, input().split())
		a = map(int, input().split())
		b = []
		for num in a:
			b.append(num)
		if k % 2 == 1:
			if p == 0:
				print(max(b))
			else:
				print(min(b))
		elif p == 0:
			_max = max(b[1], b[n - 2])
			for i in range(1, n - 1):
				_min = min(b[i - 1], b[i + 1])
				if _min > _max:
					_max = _min
			print(_max)
		else:
			_min = min(b[1], b[n - 2])
			for i in range(1, n - 1):
				_max = max(b[i - 1], b[i + 1])
				if _max < _min:
					_min = _max
			print(_min)
main()