codeforces#P2071F. Towering Arrays
Towering Arrays
Description
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.
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.
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
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$.