Rising Sand
Contest: Codeforces Round 803 (Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, greedy, implementation

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 < i < n$$$ and $$$a_i > 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?

Input format:
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$$$.

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

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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]$$$.

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$$$.

Example input:
3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1

Example output:
2
0
1

Editorial:
Note that two piles in a row can't be too tall, since a pile that is too tall has strictly more sand than its neighbours.
If $$$k=1$$$ then we can make every other pile too tall, excluding the ends of the array. For example, if $$$a=[1,2,3,4,5,6]$$$, we can make piles $$$2$$$ and $$$4$$$ too tall by performing some large number of operations on them (say, by making it into $$$[1, 10^{100}, 3, 10^{100}, 5, 6]$$$.) The answer is $$$\left\lfloor\frac{n-1}{2}\right\rfloor$$$.
If $$$k \geq 2$$$, then note that for any pile, if we perform the operation on it then we perform on one of its neighbours as well. Therefore, if the pile is not too tall initially, then it will never become too tall as a result of these operations, since both a pile and at least one of its neighbours will gain sand. So in this case, doing operations never improves the answer, and so the answer is the number of too tall piles initially.
The time complexity is $$$\mathcal{O}(n)$$$.