Вам дан массив \(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}.\(\)
Выходные данные
Для каждого набора выведите единственное число — количество индексов, удовлетворяющих условиям.
Примечание
В первом наборе оба подмассива удовлетворяют условиям:
- \(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\), так что этот подмассив не удовлетворяет условиям.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|