← 返回题目列表

Codeforces · 2071/F

F. 高耸的阵列

中文机器翻译题面 查看原题

长度为 $$$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$$$-巍峨.

示例

输入
复制

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

注意

在第一个测试用例中,您无法删除任何元素。该数组仍然是 $$$[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$$$。