一组 $$$n$$$ 正整数 $$$a_1,a_2,\ldots,a_n$$$ 从天而降,还有一个正整数 $$$k \le n$$$。
您最多可以应用以下操作 $$$k$$$ 次:
- 选择一个索引 $$$1 \le i \le n$$$ 和一个整数 $$$1 \le x \le 10^9$$$。然后执行 $$$a_i := x$$$ (将 $$$x$$$ 分配给 $$$a_i$$$)。
然后构建一个完整的无向加权图,其中 $$$n$$$ 顶点编号为 $$$1$$$ 到 $$$n$$$ 之间的整数,其中边 $$$(l, r)$$$ ($$$1 \le l < r \le n$$$) 具有权重$$$\min(a_{l},a_{l+1},\ldots,a_{r})$$$。
您必须在执行最多 $$$k$$$ 操作后找到结果图的最大可能直径。
图的直径等于 $$$\max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)}$$$,其中 $$$\operatorname{d}(u, v)$$$ 是顶点 $$$u$$$ 和顶点 $$$v$$$ 之间的最短路径的长度。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le n$$$)。
每个测试用例的第二行包含 $$$n$$$ 正整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,打印一个整数 - 执行最多 $$$k$$$ 操作后图形的最大可能直径。
示例
输入 #1
6 3 1 2 4 1 3 2 1 9 84 3 1 10 2 6 3 2 179 17 1000000000 2 1 5 9 2 2 4 2
输出 #1
4 168 10 1000000000 9 1000000000
注意
在第一个测试用例中,最佳数组之一是 $$$[2,4,5]$$$。
在此数组上构建的图:
$$$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$$$ 和 $$$\operatorname{d}(2, 3) = 4$$$,因此直径等于 $$$\max(2,2,4) = 4$$$。