F. Towering Arrays
time limit per test
6 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

An array $$$b = [b_1, b_2, \ldots, b_m]$$$ of length $$$m$$$ is called $$$p$$$-towering if there exists an index $$$i$$$ ($$$1\le i\le m$$$) such that for every index $$$j$$$ ($$$1 \le j \le m$$$), the following condition holds: $$$$$$b_j \ge p - |i - j|.$$$$$$

Given an array $$$a = [a_1, a_2, \ldots, a_n]$$$ of length $$$n$$$, you can remove at most $$$k$$$ elements from it. Determine the maximum value of $$$p$$$ for which the remaining array can be made $$$p$$$-towering.

Input

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

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

The second line contains $$$n$$$ 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 $$$2 \cdot 10^5$$$.

Output

For each test case, output a single integer — the maximum value of $$$p$$$ for which the remaining array can be made $$$p$$$-towering.

Example
Input
6
5 0
2 1 4 5 2
5 3
2 1 4 5 2
6 1
1 2 3 4 5 1
11 6
6 3 8 5 8 3 2 1 2 7 1
14 3
3 2 3 5 5 2 6 7 4 8 10 1 8 9
2 0
1 1
Output
3
5
5
7
9
1
Note

In the first test case, you cannot delete any element. The array remains $$$[2, 1, 4, \color{red}{5}, 2]$$$ and is p-towering for $$$p = 3$$$ by picking $$$i = 4$$$:

  • $$$a_1 = 2 \ge p - |i - 1| = 3 - |4 - 1| = 0$$$;
  • $$$a_2 = 1 \ge p - |i - 2| = 3 - |4 - 2| = 1$$$;
  • $$$a_3 = 4 \ge p - |i - 3| = 3 - |4 - 3| = 2$$$;
  • $$$a_4 = 5 \ge p - |i - 4| = 3 - |4 - 4| = 3$$$;
  • $$$a_5 = 2 \ge p - |i - 5| = 3 - |4 - 5| = 2$$$.

In the second test case, you can remove the first, second, and fifth elements to obtain the array $$$[4, \color{red}{5}]$$$. Clearly, the obtained array is p-towering for $$$p = 5$$$ by picking $$$i = 2$$$.