CF2071F Towering Arrays

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.

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 $ .