— Do you have a wish?

— I want people to stop gifting each other arrays.

O_o and Another Young Boy

An array of $n$ positive integers $a_1,a_2,\ldots,a_n$ fell down on you from the skies, along with a positive integer $k \le n$.

You can apply the following operation at most $k$ times:

Choose an index $1 \le i \le n$ and an integer $1 \le x \le 10^9$. Then do $a_i := x$ (assign $x$ to $a_i$).

Then build a complete undirected weighted graph with $n$ vertices numbered with integers from $1$ to $n$, where edge $(l, r)$ ($1 \le l < r \le n$) has weight $\min(a_{l},a_{l+1},\ldots,a_{r})$.

You have to find the maximum possible diameter of the resulting graph after performing at most $k$ operations.

The diameter of a graph is equal to $\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$, where $\operatorname{d}(u, v)$ is the length of the shortest path between vertex $u$ and vertex $v$.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$).

The second line of each test case contains $n$ positive integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case print one integer — the maximum possible diameter of the graph after performing at most $k$ operations.


-----Examples-----

Input
6
3 1
2 4 1
3 2
1 9 84
3 1
10 2 6
3 2
179 17 1000000000
2 1
5 9
2 2
4 2
Output
4
168
10
1000000000
9
1000000000


-----Note-----

In the first test case, one of the optimal arrays is $[2,4,5]$.

The graph built on this array:

$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$ and $\operatorname{d}(2, 3) = 4$, so the diameter is equal to $\max(2,2,4) = 4$.

Difficulty: HARD
Tags: Shortest paths

Constructive algorithms

Sorting

Greedy algorithms

Data structures
Skill types: Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == n:
		print(10 ** 9)
		continue
	b = []
	for i in range(n):
		b.append((a[i], i))
	b.sort()
	i = 0
	while k > 1:
		a[b[i][1]] = 10 ** 9
		i += 1
		k -= 1
	ans = 0
	j = i
	for i in range(1, n):
		(x, y) = (a[i - 1], a[i])
		z = b[j][0] * 2
		if i - 1 <= b[j][1] <= i:
			z = b[j + 1][0] * 2
		z1 = b[j + 1][0] * 2
		ans = max(ans, min(max(x, y), z), min(min(x, y), z1))
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	A = sorted(((a[i], i) for i in range(n)))
	if k == n:
		print(1000000000)
		continue
	for i in range(k - 1):
		a[A[i][1]] = 1000000000
	(f, g) = (A[k - 1][0], A[k][0])
	pairs = [min(a[i], a[i + 1]) for i in range(n - 1)]
	L_max = [0]
	R_max = [0]
	for i in range(n - 1):
		L_max.append(max(L_max[-1], pairs[i]))
		R_max.append(max(R_max[-1], pairs[-i - 1]))
	z = min(max(a[1], R_max[n - 2]), 2 * (f if f != a[0] else g))
	z = max(z, min(max(a[-2], L_max[n - 2]), 2 * (f if f != a[-1] else g)))
	for i in range(1, n - 1):
		z = max(z, min(max(a[i - 1], a[i + 1], L_max[i - 1], R_max[n - 2 - i]), 2 * (f if f != a[i] else g)))
	print(z)


import random
import sys
sys.setrecursionlimit(1000000000)
from collections import defaultdict, deque
from functools import lru_cache
from bisect import bisect_left, bisect_right, insort_right, insort_left
import heapq
from itertools import accumulate

def solve(n, nums, k):
	M = 10 ** 9
	Max = max(nums)

	def check(t):
		nums1 = list(nums)
		tmp = 0
		for i in range(n):
			if nums1[i] * 2 < t:
				nums1[i] = M
				tmp += 1
		if tmp > k:
			return False
		if k - tmp >= 2:
			return True
		if k - tmp == 1:
			return max(nums1) >= t
		return max((min(nums1[i], nums1[i + 1]) for i in range(n - 1))) >= t
	lo = 0
	hi = M
	while lo < hi:
		p = (lo + hi) // 2
		if not check(p):
			hi = p - 1
		else:
			if lo == p:
				break
			lo = p
	if check(hi):
		lo = hi
	return lo
for _ in range(int(input())):
	(n, k) = list(map(int, input().strip().split(' ')))
	res = solve(n, list(map(int, input().strip().split(' '))), k)
	print(res)