CF1698B.Rising Sand

There are $n$ piles of sand where the $i$-th pile has $a_i$ blocks of sand. The $i$-th pile is called too tall if $1 \lt i \lt n$ and $a_i \gt a_{i-1} + a_{i+1}$. That is, a pile is too tall if it has more sand than its two neighbours combined. (Note that piles on the ends of the array cannot be too tall.)

You are given an integer $k$. An operation consists of picking $k$ consecutive piles of sand and adding one unit of sand to them all. Formally, pick $1 \leq l,r \leq n$ such that $r-l+1=k$. Then for all $l \leq i \leq r$, update $a_i \gets a_i+1$.

What is the maximum number of piles that can simultaneously be too tall after some (possibly zero) operations?

有 $n$ 堆沙子，其中第 $i$ 堆包含 $a_i$ 个沙块。若满足 $1 \lt i \lt n$ 且 $a_i \gt a_{i-1} + a_{i+1}$，则称第 $i$ 堆沙子为「过高」。即：当某堆沙子的沙块数严格大于其左右两个相邻堆沙块数之和时，该堆即为过高。（注意：数组两端的堆不可能过高。）

给定一个整数 $k$。一次操作定义为：选择 $k$ 个连续的沙堆，并向这 $k$ 个沙堆各添加一单位沙子。形式化地，选择满足 $1 \leq l,r \leq n$ 且 $r-l+1=k$ 的区间 $[l, r]$；然后对所有 $l \leq i \leq r$，执行更新 $a_i \gets a_i+1$。

在经过若干次（可以为零次）操作后，最多能同时有多少堆沙子为「过高」？

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($3 \leq n \leq 2 \cdot 10^5$; $1 \leq k \leq n$) — the number of piles of sand and the size of the operation, respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the sizes of the piles.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 1000$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$3 \leq n \leq 2 \cdot 10^5$；$1 \leq k \leq n$），分别表示沙堆的数量和操作的大小。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示各沙堆的大小。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, output a single integer — the maximum number of piles that are simultaneously too tall after some (possibly zero) operations.

对于每个测试用例，输出一个整数——在执行若干次（可能为零次）操作后，同时过高（too tall）的堆的最大数量。

In the first test case, we can perform the following three operations:

• Add one unit of sand to piles $1$ and $2$: $[\color{red}{3}, \color{red}{10}, 2, 4, 1]$.
• Add one unit of sand to piles $4$ and $5$: $[3, 10, 2, \color{red}{5}, \color{red}{2}]$.
• Add one unit of sand to piles $3$ and $4$: $[3, 10, \color{red}{3}, \color{red}{6}, 2]$.

Now piles $2$ and $4$ are too tall, so in this case the answer is $2$. It can be shown that it is impossible to make more than $2$ piles too tall.

In the second test case, any operation will increase all piles by $1$ unit, so the number of too tall piles will always be $0$.

In the third test case, we can increase any pile by $1$ unit of sand. It can be shown that the maximum number of too tall piles is $1$.

在第一个测试用例中，我们可以执行以下三次操作：

• 向第 $1$ 和第 $2$ 堆沙子各添加一单位沙子：$[\color{red}{3}, \color{red}{10}, 2, 4, 1]$。
• 向第 $4$ 和第 $5$ 堆沙子各添加一单位沙子：$[3, 10, 2, \color{red}{5}, \color{red}{2}]$。
• 向第 $3$ 和第 $4$ 堆沙子各添加一单位沙子：$[3, 10, \color{red}{3}, \color{red}{6}, 2]$。

此时，第 $2$ 堆和第 $4$ 堆沙子过高，因此本例的答案为 $2$。可以证明，无法使超过 $2$ 堆沙子过高。

在第二个测试用例中，任意操作都会使所有沙堆高度增加 $1$ 单位，因此过高沙堆的数量恒为 $0$。

在第三个测试用例中，我们可以将任意一堆沙子的高度增加 $1$ 单位。可以证明，过高沙堆的最大数量为 $1$。