Вам дан массив \(a\) длины \(n\) и число \(k\). Посчитайте количество подмассивов \([a_i, \dots, a_{i+k}]\) (здесь \(1 \leq i \leq n - k\)) длины \(k+1\) удовлетворяющих следующим условиям:
Более формально, найдите количество индексов \(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
1000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач