JJ has an array A of size N. He can perform the following operations on the array at most K times:

Set A_{i} := A_{i + 1} where 1 ≤ i ≤ N - 1
Set A_{i} := A_{i - 1} where 2 ≤ i ≤ N

He wants to maximize the value of the minimum element of the array A. Formally, he wants to maximize the value of \min\limits_{1 ≤ i ≤ N} A_{i}.

Can you help him do so?

------ Input Format ------ 

- The first line contains a single integer T - the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and K - the size of the array A and the maximum number of operations allowed respectively.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \dots, A_{N} denoting the array A.

------ Output Format ------ 

For each test case, output the maximum value of the minimum element of the array A that can be obtained after applying the given operation at most K times.

------ Constraints ------ 

$1 ≤ T ≤ 100$
$2 ≤ N ≤ 10^{5}$
$0 ≤K ≤10^{5}$
$1 ≤A_{i} ≤10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
4
5 4
5 4 3 2 1
6 1
8 2 3 9 6 10
5 2
4 3 4 3 5
5 1000
4 3 4 3 5

----- Sample Output 1 ------ 
5
3
4
5

----- explanation 1 ------ 
Test Case 1: We can perform the following operations (in the following order):
- Set $A_{2} := A_{1}$. Array $A$ becomes $[5, 5, 3, 2, 1]$ 
- Set $A_{3} := A_{2}$. Array $A$ becomes $[5, 5, 5, 2, 1]$ 
- Set $A_{4} := A_{3}$. Array $A$ becomes $[5, 5, 5, 5, 1]$
- Set $A_{5} := A_{4}$. Array $A$ becomes $[5, 5, 5, 5, 5]$

Therefore the answer is $5$.

Test Case 2: We can perform the following operations (in the following order):
- Set $A_{2} := A_{3}$. Array $A$ becomes $[8, 3, 3, 9, 6, 10]$

Therefore the answer is $3$.

Test Case 3: We can perform the following operations (in the following order):
- Set $A_{2} := A_{3}$. Array $A$ becomes $[4, 4, 4, 3, 5]$
- Set $A_{4} := A_{3}$. Array $A$ becomes $[4, 4, 4, 4, 5]$

Therefore the answer is $4$.

Source: codechef | Difficulty: EASY


Solutions:
for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if k <= n - 1:
		print(a[k])
	else:
		print(a[n - 1])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = sorted([int(x) for x in input().split()])
	print(a[min(len(a) - 1, k)])


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	print(a[min(k, n - 1)])


t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = sorted([int(i) for i in input().split()])
	if k >= n - 1:
		print(arr[n - 1])
	else:
		print(arr[k])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if k <= n - 1:
		print(a[k])
	else:
		print(max(a))


T = int(input())
for _ in range(0, T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	if k >= len(a):
		print(a[-1])
	else:
		print(a[k])


for i in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst.sort()
	if k >= len(lst):
		print(lst[-1])
	else:
		print(lst[k])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if len(a) - 1 <= k:
		print(max(a))
	else:
		a.sort()
		for i in range(k):
			a.pop(0)
		print(a[0])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(j) for j in input().split()]
	arr.sort()
	if k >= n:
		print(arr[n - 1])
	else:
		print(arr[k])


for i in range(int(input())):
	(m, n) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if n >= m:
		print(l[-1])
	else:
		print(l[n])


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if m <= n - 1:
		print(a[m])
	else:
		print(a[n - 1])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if k >= len(a) - 1:
		print(max(a))
	else:
		for j in range(k):
			a.pop(0)
		print(min(a))


for _ in range(int(input())):
	(m, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(k, m - 1)])


for _ in range(int(input())):
	(f, g) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l1 = sorted(l1)
	print(l1[min(g, f - 1)])


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(d, n - 1)])


for _ in range(int(input())):
	(M, s) = map(int, input().split())
	B = list(map(int, input().split()))
	B = sorted(B)
	print(B[min(s, M - 1)])


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	c = list(map(int, input().split()))
	c = sorted(c)
	print(c[min(M, N - 1)])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	b = list(map(int, input().split()))
	b = sorted(b)
	print(b[min(k, n - 1)])


import math
at = int(input())
for _ in range(at):
	(an, ak) = map(int, input().split())
	aa = list(map(int, input().split()))
	aa.sort()
	if ak <= an - 1:
		print(aa[ak])
	else:
		print(aa[an - 1])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort()
	if k >= n:
		print(li[-1])
	else:
		print(li[k])


for _ in range(int(input())):
	(p, s) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if s >= p:
		print(l[-1])
	else:
		print(l[s])


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	b = list(map(int, input().split()))
	b = sorted(b)
	print(b[min(K, N - 1)])


for i in range(int(input())):
	(s, p) = map(int, input().split())
	array = list(map(int, input().split()))[:s]
	array.sort()
	if p > s:
		print(max(array))
	else:
		print(array[p])


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if k >= n:
		print(l[-1])
	else:
		print(l[k])


for _ in range(int(input())):
	(nim, kim) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(kim, nim - 1)])


for _ in range(int(input())):
	(u, q) = map(int, input().split())
	o = list(map(int, input().split()))
	o.sort()
	if q >= u:
		print(o[-1])
	else:
		print(o[q])


import math
tc = int(input())
for _ in range(tc):
	(m, p) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if p <= m - 1:
		print(a[p])
	else:
		print(a[m - 1])


t = int(input())
for i in range(t):
	(b, a) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if a >= b:
		print(l[-1])
	else:
		print(l[a])


for _ in range(int(input())):
	(r, b) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if b >= r:
		print(l[-1])
	else:
		print(l[b])


t = int(input())
for i in range(t):
	(l, n) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if n > l:
		print(a.pop())
	else:
		print(a[n])


t = int(input(''))
for _ in range(t):
	(n, k) = map(int, input('').split())
	l = input('').split()
	l = [int(x) for x in l]
	l.sort()
	print(l[min(k, n - 1)])


s = int(input())
while s > 0:
	(a, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if a - k <= 1:
		print(max(l))
	else:
		l.sort()
		print(l[(a + k) % a])
	s -= 1


A = int(input())
for i in range(A):
	(N, M) = map(int, input().split())
	List = list(map(int, input().split()))
	List.sort()
	if M >= N:
		print(List[-1])
	else:
		print(List[M])


a = int(input())
for i in range(a):
	(u, v) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if v < u:
		print(l[v])
	else:
		print(l[-1])


for _ in range(int(input())):
	(e, q) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	if q >= e:
		print(x[-1])
	else:
		print(x[q])


for h in range(int(input())):
	(ns, k56) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(k56, ns - 1)])


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	z = sorted(z)
	print(z[min(y, x - 1)])


for i in range(int(input())):
	(x, y) = map(int, input().split())
	z = list(map(int, input().split()))
	z.sort()
	if y >= x:
		print(z[-1])
	else:
		print(z[y])


for _ in range(int(input())):
	(i, j) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(j, i - 1)])


x = int(input())
for i in range(0, x):
	(h, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	a.sort()
	if k >= h:
		print(a[-1])
	else:
		print(a[k])


for _ in range(int(input())):
	(h, v) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if v >= h:
		print(l[-1])
	else:
		print(l[v])


for i in range(int(input())):
	(p, q) = map(int, input().split())
	r = list(map(int, input().split()))
	r.sort()
	if q >= p:
		print(r[-1])
	else:
		print(r[q])


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = [int(k) for k in input().split()]
	a.sort()
	print(a[min(k, n - 1)])
	t -= 1


for _ in range(int(input())):
	(s, u) = map(int, input().split())
	z = list(map(int, input().split()))
	z = sorted(z)
	print(z[min(u, s - 1)])


for i in range(int(input())):
	(x1, y1) = map(int, input().split())
	z1 = list(map(int, input().split()))
	z1.sort()
	if y1 >= x1:
		print(z1[-1])
	else:
		print(z1[y1])


te = int(input(''))
for _ in range(te):
	(n, a) = map(int, input('').split())
	l = input('').split()
	l = [int(x) for x in l]
	l.sort()
	print(l[min(n - 1, a)])


t = int(input())
while t:
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li.sort()
	if k >= n:
		print(li[-1])
	else:
		print(li[k])
	t -= 1


for _ in range(int(input())):
	(vp, up) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(up, vp - 1)])


d = int(input())
for _ in range(d):
	(mm, pp) = map(int, input().split())
	aaa = list(map(int, input().split()))
	aaa.sort()
	if pp <= mm - 1:
		print(aaa[pp])
	else:
		print(aaa[mm - 1])


for i in range(int(input())):
	(N, K) = map(int, input().split())
	l = list(map(int, input().split()))
	l.sort()
	if K >= N:
		print(l[-1])
	else:
		print(l[K])


t = int(input())
for _ in range(t):
	(m, p) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if p <= m - 1:
		print(a[p])
	else:
		print(a[m - 1])


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	P = list(map(int, input().split()))
	P.sort()
	if b >= a:
		print(P[-1])
	else:
		print(P[b])


for _ in range(int(input())):
	(ap, bp) = map(int, input().split())
	a = list(map(int, input().split()))
	a = sorted(a)
	print(a[min(bp, ap - 1)])


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = list(map(int, input().split()))
	c.sort()
	if b >= a:
		print(c[-1])
	else:
		print(c[b])


for p in range(int(input())):
	(x, y) = map(int, input().split())
	g = list(map(int, input().split()))
	g = sorted(g)
	print(g[min(y, x - 1)])


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	array = list(map(int, input().split()))[:n]
	array.sort()
	if p > n:
		print(max(array))
	else:
		print(array[p])


for _ in range(int(input())):
	(ammu, chikku) = map(int, input().split())
	que = list(map(int, input().split()))
	que.sort()
	if chikku >= ammu:
		print(que[-1])
	else:
		print(que[chikku])


for i in range(int(input())):
	(x, z) = map(int, input().split())
	k = list(map(int, input().split()))
	k = sorted(k)
	print(k[min(z, x - 1)])


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	a.sort()
	if k > n:
		print(max(a))
	else:
		print(a[k])


for smart in range(int(input())):
	(nani, tato) = map(int, input().split())
	vivo = list(map(int, input().split()))
	vivo.sort()
	if tato >= nani:
		print(vivo[-1])
	else:
		print(vivo[tato])


for veena in range(int(input())):
	(nittu, kittu) = map(int, input().split())
	littu = list(map(int, input().split()))
	littu.sort()
	if kittu >= nittu:
		print(littu[-1])
	else:
		print(littu[kittu])


for i in range(int(input())):
	(a, b) = map(int, input().split())
	k = list(map(int, input().split()))
	k = sorted(k)
	print(k[min(b, a - 1)])


n = int(input())
for i in range(1, n + 1):
	(x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if y >= x:
		print(a[-1])
	else:
		print(a[y])


for i in range(int(input())):
	(a, b) = map(int, input().split())
	h = list(map(int, input().split()))
	h = sorted(h)
	c = min(b, a - 1)
	print(h[c])


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if n - k <= 1:
		print(max(l))
	else:
		l.sort()
		print(l[(n + k) % n])
	t -= 1


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	x.sort()
	if k <= n - 1:
		print(x[k])
	else:
		print(x[n - 1])