二的幂排序

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的数组 $a$ 和一个整数 $k$，请你求出有多少个下标 $1 \leq i \leq n - k$，使得长度为 $k+1$ 的子数组 $[a_i, \dots, a_{i+k}]$（注意长度为 $k+1$，不是 $k$）满足以下性质：

• 如果将第一个元素乘以 $2^0$，第二个元素乘以 $2^1$，……，第 $k+1$ 个元素乘以 $2^k$，那么这个子数组是严格递增的。

更正式地说，统计有多少个下标 $1 \leq i \leq n - 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 \times 10^5$，$1 \leq k < n$），分别表示数组的长度和不等式的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 10^9$），表示数组的元素。

所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示满足题目条件的下标数量。

样例输入 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

样例输出 1

2
3
2
3
1
0

数据范围

对于所有数据，$1\le t\le1000$，$3\le n\le2\times10^5$，$1\le k<n$，$1\le a_i\le10^9$；所有测试用例中 $n$ 的总和不超过 $2\times10^5$。

子任务编号	分值	特殊限制
1	30	$n\le20$
2		$k=1$
3	40	无特殊限制