CF1712D.Empty Graph

— Do you have a wish?

— I want people to stop gifting each other arrays.

O_o and Another Young Boy

An array of $n$ positive integers $a_1,a_2,\ldots,a_n$ fell down on you from the skies, along with a positive integer $k \le n$.

You can apply the following operation at most $k$ times:

• Choose an index $1 \le i \le n$ and an integer $1 \le x \le 10^9$. Then do $a_i := x$ (assign $x$ to $a_i$).

Then build a complete undirected weighted graph with $n$ vertices numbered with integers from $1$ to $n$, where edge $(l, r)$ ($1 \le l \lt r \le n$) has weight $\min(a_{l},a_{l+1},\ldots,a_{r})$.

You have to find the maximum possible diameter of the resulting graph after performing at most $k$ operations.

The diameter of a graph is equal to $\max\limits_{1 \le u \lt v \le n}{\operatorname{d}(u, v)}$, where $\operatorname{d}(u, v)$ is the length of the shortest path between vertex $u$ and vertex $v$.

— 你有什么愿望吗？
— 我希望人们停止互相赠送数组。

O_o 和另一位少年

一个包含 $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$（即把 $a_i$ 赋值为 $x$）。

接着，构造一个具有 $n$ 个顶点（编号为 $1$ 到 $n$）的完全无向带权图，其中边 $(l, r)$（满足 $1 \le l \lt r \le n$）的权重为 $\min(a_{l},a_{l+1},\ldots,a_{r})$。

你需要求出：在至多执行 $k$ 次上述操作后，所得图的最大可能直径。

图的直径定义为 $\max\limits_{1 \le u \lt v \le n}{\operatorname{d}(u, v)}$，其中 $\operatorname{d}(u, v)$ 表示顶点 $u$ 与顶点 $v$ 之间的最短路径长度。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 10^5$, $1 \le k \le n$).

The second line of each test case contains $n$ positive 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 $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case print one integer — the maximum possible diameter of the graph after performing at most $k$ operations.

对于每个测试用例，输出一个整数——执行至多 $k$ 次操作后图的最大可能直径。

In the first test case, one of the optimal arrays is $[2,4,5]$.

The graph built on this array:

$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$ and $\operatorname{d}(2, 3) = 4$, so the diameter is equal to $\max(2,2,4) = 4$.

在第一个测试用例中，一个最优数组是 $[2,4,5]$。

基于该数组构建的图：

$\operatorname{d}(1, 2) = \operatorname{d}(1, 3) = 2$，且 $\operatorname{d}(2, 3) = 4$，因此直径等于 $\max(2,2,4) = 4$。