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.
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$$$.
For each test case, output a single integer — the maximum value of $$$p$$$ for which the remaining array can be made $$$p$$$-towering.
65 02 1 4 5 25 32 1 4 5 26 11 2 3 4 5 111 66 3 8 5 8 3 2 1 2 7 114 33 2 3 5 5 2 6 7 4 8 10 1 8 92 01 1
3 5 5 7 9 1
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$$$:
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$$$.