B. Песочные вершины
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перед вами $$$n$$$ кучек песка, и в $$$i$$$-й кучке ровно $$$a_i$$$ песчинок. Назовем $$$i$$$-ю кучку слишком высокой, если $$$1 < i < n$$$, и $$$a_i > a_{i-1} + a_{i+1}$$$. Иными словами кучка слишком высокая, если в ней больше песка, чем в двух соседних вместе. (Обратите внимание, что кучки по краям не могут быть слишком высокими.)

Вам дано целое число $$$k$$$. За одну операцию вы можете выбрать $$$k$$$ последовательных кучек и добавить к каждой из них одну песчинку. Формально, выберите $$$1 \leq l,r \leq n$$$ такие, что $$$r-l+1=k$$$. Затем для всех $$$l \leq i \leq r$$$ обновите $$$a_i \gets a_i+1$$$.

Какое максимальное количество кучек одновременно может быть слишком высокими после нескольких (возможно, нуля) операций?

Входные данные

Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимальное количество кучек, которые одновременно могут быть слишком высокими после нескольких (возможно, нуля) операций.

Пример
Входные данные
3
5 2
2 9 2 4 1
4 4
1 3 2 1
3 1
1 3 1
Выходные данные
2
0
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$$$.