G. 2^Сортировка
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив $$$a$$$ длины $$$n$$$ и число $$$k$$$. Посчитайте количество подмассивов $$$[a_i, \dots, a_{i+k}]$$$ (здесь $$$1 \leq i \leq n - k$$$) длины $$$k+1$$$ удовлетворяющих следующим условиям:

  • Если умножить первый элемент подмассива на $$$2^0$$$, второй на $$$2^1$$$, ..., и ($$$k+1$$$)-й элемент на $$$2^k$$$, то этот подмассив будет строго возрастающим.

Более формально, найдите количество индексов $$$1 \leq i \leq n - k$$$ таких, что удовлетворяется $$$k$$$ неравенств: $$$$$$2^0 \cdot a_i < 2^1 \cdot a_{i+1} < 2^2 \cdot a_{i+2} < \dots < 2^k \cdot a_{i+k}.$$$$$$

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

Первая строка содержит единственное число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных.

В первой строке каждого набора содержатся два целых числа $$$n$$$, $$$k$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k < n$$$).

Во второй строке каждого набора содержатся $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — элементы массива.

Сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора выведите единственное число — количество индексов, удовлетворяющих условиям.

Пример
Входные данные
6
4 2
20 22 19 84
5 1
9 5 3 2 1
5 2
9 5 3 2 1
7 2
22 12 16 4 3 22 12
7 3
22 12 16 4 3 22 12
9 3
3 9 12 3 9 12 3 9 12
Выходные данные
2
3
2
3
1
0
Примечание

В первом наборе оба подмассива удовлетворяют условиям:

  • $$$i=1$$$: помассив $$$[a_1,a_2,a_3] = [20,22,19]$$$, и $$$1 \cdot 20 < 2 \cdot 22 < 4 \cdot 19$$$.
  • $$$i=2$$$: подмассив $$$[a_2,a_3,a_4] = [22,19,84]$$$, и $$$1 \cdot 22 < 2 \cdot 19 < 4 \cdot 84$$$.
Во втором наборе три подмассива удовлетворяют условиям:
  • $$$i=1$$$: подмассив $$$[a_1,a_2] = [9,5]$$$, и $$$1 \cdot 9 < 2 \cdot 5$$$.
  • $$$i=2$$$: подмассив $$$[a_2,a_3] = [5,3]$$$, и $$$1 \cdot 5 < 2 \cdot 3$$$.
  • $$$i=3$$$: подмассив $$$[a_3,a_4] = [3,2]$$$, и $$$1 \cdot 3 < 2 \cdot 2$$$.
  • $$$i=4$$$: подмассив $$$[a_4,a_5] = [2,1]$$$, но $$$1 \cdot 2 = 2 \cdot 1$$$, так что этот подмассив не удовлетворяет условиям.