长度为 $$$m$$$ 的数组 $$$b = [b_1, b_2, \ldots, b_m]$$$ 称为 $$$p$$$-巍峨 如果存在索引 $$$i$$$ ($$$1\le i\le m$$$),则对于每个索引 $$$j$$$ ($$$1 \le j \le m$$$),以下条件成立:$$b_j \ge p - |i - j|.$$
给定一个长度为 $$$n$$$ 的数组 $$$a = [a_1, a_2, \ldots, a_n]$$$,您最多可以从中删除 $$$k$$$ 个元素。确定$$$p$$$的最大值,剩余数组可以由$$$p$$$-巍峨.
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$0 \le k \lt n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - $$$p$$$ 的最大值,剩余数组可以由 $$$p$$$-巍峨.
示例
输入复制
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
注意
在第一个测试用例中,您无法删除任何元素。该数组仍然是 $$$[2, 1, 4, \color{red}{5}, 2]$$$ 并且是 p-高耸 对于 $$$p = 3$$$,选择 $$$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$$$。
在第二个测试用例中,可以删除第一、第二、第五个元素,得到数组$$$[4, \color{red}{5}]$$$。显然,得到的数组为 p-高耸 $$$p = 5$$$ 通过选择 $$$i = 2$$$。