Given an array $a$ of length $n$ and an integer $k$, find the number of indices $1 \leq i \leq n - k$ such that the subarray $[a_i, \dots, a_{i+k}]$ with length $k+1$ (not with length $k$) has the following property:

If you multiply the first element by $2^0$, the second element by $2^1$, ..., and the ($k+1$)-st element by $2^k$, then this subarray is sorted in strictly increasing order.

More formally, count the number of indices $1 \leq i \leq n - k$ such that $$2^0 \cdot a_i < 2^1 \cdot a_{i+1} < 2^2 \cdot a_{i+2} < \dots < 2^k \cdot a_{i+k}.$$


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The first line of each test case contains two integers $n$, $k$ ($3 \leq n \leq 2 \cdot 10^5$, $1 \leq k < n$) — the length of the array and the number of inequalities.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the elements of the array.

The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output a single integer — the number of indices satisfying the condition in the statement.


-----Examples-----

Input
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
Output
2
3
2
3
1
0


-----Note-----

In the first test case, both subarrays satisfy the condition:

$i=1$: the subarray $[a_1,a_2,a_3] = [20,22,19]$, and $1 \cdot 20 < 2 \cdot 22 < 4 \cdot 19$.

$i=2$: the subarray $[a_2,a_3,a_4] = [22,19,84]$, and $1 \cdot 22 < 2 \cdot 19 < 4 \cdot 84$.

In the second test case, three subarrays satisfy the condition:

$i=1$: the subarray $[a_1,a_2] = [9,5]$, and $1 \cdot 9 < 2 \cdot 5$.

$i=2$: the subarray $[a_2,a_3] = [5,3]$, and $1 \cdot 5 < 2 \cdot 3$.

$i=3$: the subarray $[a_3,a_4] = [3,2]$, and $1 \cdot 3 < 2 \cdot 2$.

$i=4$: the subarray $[a_4,a_5] = [2,1]$, but $1 \cdot 2 = 2 \cdot 1$, so this subarray doesn't satisfy the condition.

Difficulty: MEDIUM
Tags: Dynamic programming

Data structures

Sorting

Amortized analysis
Skill types: Dynamic programming

Amortized analysis

Sorting

Data structures

Starter code:

Solutions:
def solve():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 0
	ct = 1
	for i in range(1, n):
		if 2 * l[i] > l[i - 1]:
			ct += 1
		else:
			ct = 1
		if ct > k:
			ans += 1
	print(ans)
for t in range(int(input())):
	solve()


import collections
import math
import sys
from queue import PriorityQueue
from random import randint

def main(testnumber):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 1
	ans = 0
	for i in range(1, n):
		if a[i] * 2 > a[i - 1]:
			c += 1
		else:
			ans += max(0, c - k)
			c = 1
	ans += max(0, c - k)
	print(ans)
t = int(input())
cnt = 1
while t > 0:
	main(cnt)
	cnt += 1
	t -= 1


n = int(input())
for i in range(n):
	l = list(map(int, input().split()))
	long = l[0]
	equ = l[1]
	s = list(map(int, input().split()))
	s.append(0)
	num = 0
	tip = []
	ans = 0
	for j in range(long):
		if s[j] < 2 * s[j + 1]:
			num += 1
		else:
			tip.append(num)
			num = 0
	for p in tip:
		if p >= equ:
			ans += p - equ + 1
	print(ans)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	lis = list(map(int, input().split()))
	ans = 0
	c = 1
	an = ''
	for i in range(a - 1):
		if lis[i] < 2 * lis[i + 1]:
			c += 1
		else:
			if c - b > 0:
				ans += c - b
			c = 1
	if c - b > 0:
		ans += c - b
	print(ans)


def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 0
	count = 1
	k += 1
	for i in range(1, n):
		if arr[i] * 2 > arr[i - 1]:
			count += 1
		else:
			if count >= k:
				ans += count - k + 1
			count = 1
	if count >= k:
		ans += count - k + 1
	print(ans)
for T in range(int(input())):
	solve()


from math import inf, gcd, log, log2, floor, ceil, sqrt
from collections import Counter, defaultdict
from heapq import heappush, heappop, heapify
from functools import lru_cache
from itertools import accumulate
import sys
DIRS = [[1, 0], [0, 1], [0, -1], [-1, 0], [-1, -1], [1, 1], [-1, 1], [1, -1]]
MOD = 10 ** 9 + 7
input = sys.stdin.readline

def read1():
	return int(input())

def read():
	A = [int(x) for x in input().split()]
	return A
t = read1()

def solve():
	(N, K) = read()
	A = read()
	run = 1
	curr = A[0]
	runs = []
	for x in A[1:]:
		if curr < x * 2:
			curr = x
			run += 1
		else:
			runs.append(run)
			run = 1
			curr = x
	runs.append(run)
	ans = 0
	for x in runs:
		ans += max(0, x - K)
	print(ans)
while t:
	solve()
	t -= 1


def solve():
	(n, k) = map(int, input().split())
	lis = list(map(int, input().split()))
	ans = 0
	cnt = 1
	for i in range(1, n):
		if 2 * lis[i] > lis[i - 1]:
			cnt += 1
			if cnt > k:
				ans += 1
		else:
			cnt = 1
	print(ans)
for _ in range(int(input())):
	solve()


import itertools
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(sum((max(sum((1 for _ in g)) + 1 - k, 0) for (t, g) in itertools.groupby((i < j + j for (i, j) in zip(a, a[1:]))) if t)))


def sol():
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	tl = [0] * n
	tl[0] = 1
	ans = 0
	for i in range(1, n):
		if 2 * l[i] > l[i - 1]:
			tl[i] = tl[i - 1] + 1
		else:
			tl[i] = 1
	for i in tl:
		if i > k:
			ans += 1
	print(ans)
for t in range(int(input())):
	sol()


def solve():
	(n, k) = map(int, input().split())
	n += 1
	a = list(map(int, input().split())) + [-1]
	ans = 0
	cnt = 1
	for i in range(1, n):
		if a[i] * 2 > a[i - 1]:
			cnt += 1
		else:
			ans += max(0, cnt - k)
			cnt = 1
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


def p2Arr():
	x = int(input())
	for __ in range(x):
		[n, k] = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		c = 1
		fn = 0
		for i in range(1, len(arr)):
			c += 1 if 2 * arr[i] > arr[i - 1] else -1 * (c - 1)
			if c >= k + 1:
				fn += 1
		print(fn)
p2Arr()


def solve():
	(n, k) = map(int, input().split())
	a = map(int, input().split())
	a = list(a)
	res = 0
	t = 1
	i = 1
	while i < n:
		while i < n and a[i - 1] < a[i] * 2:
			i = i + 1
			t = t + 1
		if t >= k + 1:
			res = res + t - k
		t = 1
		i = i + 1
	print(res)
T = int(input())
for i in range(T):
	solve()


def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	anchor = 0
	count = 0
	for i in range(1, n):
		if a[i] * 2 <= a[i - 1]:
			anchor = i
		if i - anchor == k:
			count += 1
			anchor += 1
	print(count)

def main():
	t = int(input())
	for i in range(t):
		solve()
main()


from collections import deque

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def solve(arr, n, k):
	counts = []
	count = 0
	for i in range(1, n):
		if arr[i] * 2 > arr[i - 1]:
			count += 1
		else:
			counts.append(count + 1)
			count = 0
	if count:
		counts.append(count + 1)
	result = 0
	for c in counts:
		if c >= k + 1:
			result += c - k
	return result
n = inp()
while n:
	(m, k) = invr()
	arr = inlt()
	print(solve(arr, m, k))
	n -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	streak = 1
	ans = 0
	for i in range(1, n):
		if arr[i - 1] < arr[i] * 2:
			streak += 1
		else:
			ans += max(streak - k, 0)
			streak = 1
	ans += max(streak - k, 0)
	print(ans)


from functools import lru_cache
import sys

@lru_cache(maxsize=None)
def power(x, y):
	if y == 0:
		return 1
	temp = power(x, y // 2)
	result = temp * temp if y % 2 == 0 else temp * temp * x
	return result
input = sys.stdin.readline
t = int(input())
result = []
for _ in range(t):
	(n, k) = map(int, input().split())
	array = list(map(int, input().split()))
	k += 1

	def solve():
		(startIdx, count) = (0, 0)
		(inc, lastNum) = (0, None)
		for (endIdx, num) in enumerate(array):
			if lastNum is not None and num * 2 <= lastNum:
				startIdx = endIdx
			elif endIdx - startIdx + 1 == k:
				count += 1
				startIdx += 1
			lastNum = num
		return count
	print(solve())


def sort_2(n, k, l):
	c = 1
	i = 1
	ans = 0
	while i < n:
		if 2 * l[i] > l[i - 1]:
			c += 1
		else:
			c = 1
		if c >= k + 1:
			ans += 1
		i += 1
	return ans
for i in range(int(input())):
	[n, k] = list(map(int, input().split()))
	l = list(map(int, input().split()))
	print(sort_2(n, k, l))


def solve():
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	t = []
	for (i, v) in enumerate(arr[:-1]):
		if arr[i + 1] * 2 > v:
			t.append(True)
		else:
			t.append(False)
	res = 0
	f = sum((1 if not i else 0 for i in t[:k]))
	if f == 0:
		res += 1
	for (i, v) in enumerate(t[k:]):
		if not v:
			f += 1
		if not t[i]:
			f -= 1
		if not f:
			res += 1
	return res

def main():
	for _ in range(int(input())):
		print(solve())
	return
main()


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	c = 0
	v = 0
	for i in range(n - 1):
		if lis[i] >= 2 * lis[i + 1]:
			c += max(v - k + 1, 0)
			v = 0
		else:
			v += 1
	c += max(v - k + 1, 0)
	print(c)


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt = 1
	ans = 0
	for i in range(1, n):
		if a[i - 1] < 2 * a[i]:
			cnt += 1
		else:
			cnt = 1
		if cnt > k:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	ans = 0
	for i in range(n - 1):
		if a[i] / a[i + 1] < 2:
			c += 1
			if c >= k:
				ans += 1
		else:
			c = 0
	print(ans)


tt = int(input())
for i in range(tt):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 1
	ans = 0
	for j in range(1, n):
		if 2 * l[j] > l[j - 1]:
			c += 1
		else:
			c = 1
		if c > m:
			ans += 1
	print(ans)


import itertools
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a.append(0)
	cnt = 0
	res = 0
	for i in range(n):
		if a[i] < 2 * a[i + 1]:
			cnt += 1
		else:
			if cnt >= k:
				res += cnt - k + 1
			cnt = 0
	print(res)


a = int(input())
for y in range(a):
	(b, c) = map(int, input().split())
	d = list(map(int, input().split()))
	l = 0
	f = 1
	o = 0
	for y in range(1, b - c):
		if 2 * d[y] <= d[y - 1]:
			l = y
			if f - (c + 1) + 1 > 0:
				o += f - (c + 1) + 1
			f = 1
		else:
			f += 1
	k = b - c - l + 1
	for y in range(b - c, b):
		if 2 * d[y] > d[y - 1]:
			k += 1
		else:
			break
	j = 0
	if k - (c + 1) > 0:
		j += k - (c + 1)
	print(j + o)


t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	cur = 1
	for i in range(n - 1):
		if cur < k:
			if a[i] < a[i + 1] * 2:
				cur += 1
			else:
				cur = 1
		elif a[i] < a[i + 1] * 2:
			ans += 1
		else:
			cur = 1
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	d = [*map(int, input().split())]
	s = t = 0
	for i in range(n - 1):
		if d[i] < d[i + 1] * 2:
			t += 1
		else:
			t = 0
		if t >= k:
			s += 1
	print(s)


p = lambda : map(int, input().split())

def solve():
	(n, k) = p()
	a = [*p()]
	b = [a[i] < 2 * a[i + 1] for i in range(n - 1)]
	cnt = 0
	s = 0
	for i in range(k):
		s += b[i]
	i = 0
	j = k
	if s == k:
		cnt += 1
	while j < n - 1:
		s += b[j]
		s -= b[i]
		if s == k:
			cnt += 1
		i += 1
		j += 1
	print(cnt)
t = int(input())
for _ in range(t):
	solve()


from collections import Counter
for test in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	chain = 1
	ans = 0
	for i in range(1, n):
		if 2 * a[i] > a[i - 1]:
			chain += 1
		else:
			ans += max(0, chain - k)
			chain = 1
	ans += max(0, chain - k)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().strip().split()]
	a = [int(i) for i in input().strip().split()]
	i = 0
	j = 1
	ans = 0
	while j < n:
		while j < n and a[j] / a[j - 1] > 0.5:
			j += 1
		if j - i >= k + 1:
			ans += j - i - k
		i = j
		j = i + 1
	print(ans)


def solve():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	i = 1
	x = 1
	ans = 0
	ct = 1
	while i < n:
		if arr[i - 1] * x < arr[i] * x * 2:
			ct += 1
		else:
			if ct >= k:
				ans += ct - k
			ct = 1
			x = 1
		i += 1
	if ct >= k:
		ans += ct - k
	print(ans)
t = int(input())
for i in range(t):
	solve()


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	pre = a[0]
	cnt = 0
	ans = 0
	for cur in a[1:]:
		if pre < 2 * cur:
			cnt += 1
		else:
			cnt = 0
		if cnt >= k:
			ans += 1
		pre = cur
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	b = ''
	for i in range(n - 1):
		if l[i] < 2 * l[i + 1]:
			b += '1'
		else:
			b += '0'
	x = b.split('0')
	ans = 0
	for i in x:
		temp = len(i)
		if k > temp:
			continue
		elif k == temp:
			ans += 1
		else:
			ans += temp - k + 1
	print(ans)


q = int(input())
while q > 0:
	q -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	cnt = 1
	res = 0
	for i in range(1, n):
		if a[i - 1] < 2 * a[i]:
			cnt += 1
		else:
			cnt = 1
		if cnt > k:
			res += 1
	print(res)


strng = lambda : input()
inp = lambda : int(input())
mul = lambda : map(int, input().split())
jn = lambda x, l: x.join(map(str, l))
strlst = lambda : list(input())
lst = lambda : list(map(int, input().split()))
dd = lambda : defaultdict(lambda : 0)
import sys
input = sys.stdin.readline
from collections import defaultdict
from math import ceil, log, floor, sqrt, gcd, log10
for _ in range(inp()):
	(n, k) = mul()
	a = lst()
	cnt = 1
	ans = 0
	for i in range(1, n):
		if 2 * a[i] > a[i - 1]:
			cnt += 1
		else:
			cnt = 1
		if cnt >= k + 1:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	prev = arr[0]
	cnt = 0
	ans = 0
	for i in range(1, n):
		if arr[i] > prev // 2:
			if cnt == k - 1:
				ans += 1
			else:
				cnt += 1
		else:
			cnt = 0
		prev = arr[i]
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	cnt = 0
	temp = 0
	last = 0
	i = 1
	for a in map(int, input().split()):
		if a * 2 > last:
			temp += 1
			if i == n:
				cnt += max(0, temp - k)
		else:
			cnt += max(0, temp - k)
			temp = 1
		last = a
		i += 1
	print(cnt)


x = int(input())

def cal(n, k, arr):
	ans = 0
	t = 0
	for i in range(1, n):
		if arr[i] * 2 > arr[i - 1]:
			if i == n - 1:
				ans += max(0, i - t - k + 1)
		else:
			ans += max(0, i - t - k)
			t = i
	return ans
for jj in range(x):
	(n, k) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, k, arr))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	cnt = 0
	l = 1
	for i in range(n - 1):
		if 2 * A[i + 1] > A[i]:
			l += 1
		else:
			cnt += max(l - k, 0)
			l = 1
	if l > 1:
		cnt += max(l - k, 0)
	print(cnt)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	l = 0
	count = 0
	for r in range(1, len(nums)):
		if nums[r] * 2 <= nums[r - 1]:
			l = r
		if r - l >= k:
			count += 1
	print(count)


testcases = int(input())
for _ in range(testcases):
	(n, k) = map(int, input().split())
	lists = list(map(int, input().split()))
	(result, dos) = (0, 0)
	for i in range(1, n):
		if lists[i] > lists[i - 1] / 2:
			dos += 1
			if dos >= k:
				result += 1
		else:
			dos = 0
	print(result)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	count = 1
	result = 0
	for i in range(1, n):
		if nums[i] * 2 > nums[i - 1]:
			count += 1
		else:
			count = 1
		if count > k:
			result += 1
	print(result)


testcase = int(input())
for _ in range(testcase):
	(n, k) = list(map(int, input().split()))
	lists = list(map(int, input().split()))
	left = 0
	count = 0
	for right in range(1, len(lists)):
		if lists[right] * 2 <= lists[right - 1]:
			left = right
		if right - left >= k:
			count += 1
	print(count)


t = int(input())
for case in range(t):
	(n, k) = map(int, input().split(' '))
	arr = list(map(int, input().split(' ')))
	consecutive = 0
	count = 0
	for j in range(n - 1):
		if arr[j] < 2 * arr[j + 1]:
			if consecutive < k:
				consecutive += 1
			if consecutive == k:
				count += 1
		else:
			consecutive = 0
	print(count)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	lst = list(map(int, input().split()))
	ct = 0
	ans = 0
	for i in range(1, n):
		if lst[i] * 2 > lst[i - 1]:
			ct += 1
		else:
			ct = 0
		if ct >= k:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	le = 1
	ans = 0
	for i in range(1, n):
		if l[i] * 2 > l[i - 1]:
			le += 1
		else:
			ans += max(0, le - m)
			le = 1
	ans += max(0, le - m)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	c = 0
	hit_count = 1
	for i in range(n - 1):
		if 2 * l[i + 1] > l[i]:
			hit_count += 1
		else:
			hit_count = 1
		if hit_count >= k + 1:
			c += 1
	print(c)


import sys

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()
t = int(input())
for _ in range(t):
	(n, k) = get_ints()
	arr = get_list()
	cnt = 0
	l = 0
	for i in range(1, n):
		if 2 * arr[i] > arr[i - 1]:
			if i - l == k:
				cnt += 1
				l += 1
		else:
			l = i
	print(cnt)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	lsty = list(map(int, input().split()))
	counter = 0
	found = 0
	for j in range(a - 1):
		if lsty[j + 1] > lsty[j] / 2:
			found += 1
		else:
			found = 0
		if found == b:
			found -= 1
			counter += 1
	print(counter)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	m = 0
	for i in range(n - 1):
		if a[i] < a[i + 1] * 2:
			m += 1
			if m >= k:
				s += 1
		else:
			m = 0
	print(s)


n = int(input())
while n > 0:
	(x, y) = map(int, input().split())
	l1 = list(map(int, input().strip().split()))
	l2 = l1
	l2 = [x * 2 for x in l2]
	ans = 0
	k = 0
	for i in range(0, x - 1):
		if l1[i] < l2[i + 1]:
			k += 1
		else:
			k = 0
		if k >= y:
			ans += 1
	print(ans)
	n -= 1


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def shift(s):
	for i in range(1, len(s) + 1):
		if s == s[i:] + s[:i]:
			return i
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	cur = 1
	ans = 0
	for i in range(1, n):
		if a[i - 1] < 2 * a[i]:
			cur += 1
		else:
			cur = 1
		if cur > k:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	k += 1
	a = [int(x) for x in input().split()]
	broken = [-1] + [i for i in range(n - 1) if a[i] >= 2 * a[i + 1]] + [n - 1]
	print(sum((max(0, broken[i + 1] - broken[i] - k + 1) for i in range(len(broken) - 1))))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	sum = 0
	ans = 0
	for i in range(1, n):
		if a[i] > a[i - 1] / 2:
			sum += 1
		else:
			sum = 0
		if sum >= k:
			ans += 1
	print(ans)


tc = int(input())
for _ in range(tc):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	l = []
	cnt1 = 1
	for i in range(len(a) - 1):
		if a[i] < 2 * a[i + 1]:
			cnt1 += 1
		elif a[i] >= 2 * a[i + 1]:
			l.append(cnt1)
			cnt1 = 1
	l.append(cnt1)
	cnt = 0
	for i in l:
		if i >= k + 1:
			cnt += i - (k + 1) + 1
	print(cnt)


t = int(input())
while t:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	le = 1
	ans = 0
	for i in range(n - 1):
		if 2 * l[i + 1] > l[i]:
			le += 1
		else:
			le = 1
		if le >= k + 1:
			ans += 1
	print(ans)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	a = [a[i + 1] * 2 > a[i] for i in range(n - 1)]
	s = sum(a[:k])
	count = int(s == k)
	for i in range(n - k - 1):
		s += a[i + k] - a[i]
		if s == k:
			count += 1
	print(count)


t = int(input())
for i in range(t):
	[n, k] = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	length = 0
	ans = 0
	for i in range(n):
		if i == n - 1:
			if length >= k:
				ans += length + 1 - k
			break
		if arr[i] < 2 * arr[i + 1]:
			length += 1
		else:
			if length >= k:
				ans += length + 1 - k
			length = 0
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	answer = 0
	ran = 1
	for i in range(n - 1):
		if a[i] < a[i + 1] * 2:
			ran += 1
		else:
			ran = 1
		if ran >= k + 1:
			answer += 1
	print(answer)


import sys
sys.setrecursionlimit(10 ** 6)
from sys import stdin, stdout
I = stdin.readline
O = stdout.write

def bi(n):
	return bin(n).replace('0b', '')

def solve():
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	fin = [1 for i in range(n)]
	for i in range(1, n):
		if 2 * arr[i] <= arr[i - 1]:
			fin[i] = 0
	for i in range(1, n):
		fin[i] += fin[i - 1]
	ans = 0
	for i in range(n - k):
		if fin[i + k] - fin[i] == k:
			ans += 1
	print(ans)
for tc in range(int(input())):
	solve()


for h in range(int(input())):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	i = 0
	c = 0
	for j in range(1, n):
		if x[j] * 2 <= x[j - 1]:
			c += max(0, j - i - k)
			i = j
	c += max(0, n - i - k)
	print(c)


for _ in [0] * int(input()):
	(n, k) = map(int, input().split())
	(*a,) = map(int, input().split())
	t = 0
	b = [i for i in range(n - 1) if a[i] >= 2 * a[i + 1]]
	m = len(b)
	if m == 0:
		print(n - k)
		continue
	for i in range(m - 1):
		t += max(0, b[i + 1] - b[i] - k)
	print(t + max(0, b[0] - k + 1) + max(0, n - b[-1] - k - 1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	j = 0
	ans = 0
	for i in range(1, n):
		if 2 * l[i] > l[i - 1]:
			v = 10
		else:
			j = i
		if i - j == k:
			ans += 1
			j += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	r = 0
	prev = a[0]
	first = 0
	last = 0
	i = 1
	while i < n:
		if a[i] * 2 > a[i - 1]:
			last += 1
		else:
			r += max(0, last - first + 1 - k)
			(first, last) = (i, i)
		i += 1
	r += max(0, last - first + 1 - k)
	print(r)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	l = []
	for i in range(1, n):
		if 2 * arr[i] > arr[i - 1]:
			l.append(1)
		else:
			l.append(0)
	cs = sum(l[:k])
	ans = 0
	if cs == k:
		ans += 1
	for i in range(k, n - 1):
		cs += l[i]
		cs -= l[i - k]
		if cs == k:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	dp = [1 for i in range(n)]
	count = 0
	for i in range(1, n):
		if 2 * a[i] > a[i - 1]:
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = 1
		if dp[i] > k:
			count += 1
	print(count)


for _ in range(int(input())):
	(z, y) = map(int, input().split())
	x = list(map(int, input().split()))
	r = 0
	prev = x[0]
	first = 0
	last = 0
	a = 1
	while a < z:
		if x[a] * 2 > x[a - 1]:
			last += 1
		else:
			r += max(0, last - first + 1 - y)
			(first, last) = (a, a)
		a += 1
	r += max(0, last - first + 1 - y)
	print(r)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	s = list(map(int, input().split()))
	ans = 0
	start = 0
	end = 1
	count = 0
	while end < n:
		if s[end] * 2 > s[end - 1]:
			end += 1
			count += 1
			if count == k:
				ans += 1
				start += 1
				count -= 1
		else:
			start = end
			end = start + 1
			count = 0
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	s = []
	for i in range(n - 1):
		if a[i] < 2 * a[i + 1]:
			s.append(1)
		else:
			s.append(0)
	cnt = 0
	now = sum(s[:k])
	if now == k:
		cnt += 1
	for i in range(k, len(s)):
		now -= s[i - k]
		now += s[i]
		if now == k:
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [2 * a[i] > a[i - 1] for i in range(1, n)]
	colT = sum((b[i] for i in range(k)))
	ans = 0
	if colT == k:
		ans += 1
	for i in range(1, n - k):
		colT += b[i + k - 1] - b[i - 1]
		if colT == k:
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	nums = [int(i) for i in input().split()]
	(leftMult, rightMult) = (1, 2)
	left = 0
	count = 1
	ans = 0
	for right in range(1, n):
		cond = nums[right - 1] * leftMult < nums[right] * rightMult
		if cond:
			count += 1
		else:
			count = 1
		if count > k:
			ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * (n - 1)
	for i in range(n - 1):
		if 2 * a[i + 1] > a[i]:
			b[i] = 1
	c = sum(b[:k])
	r = 0
	if c == k:
		r += 1
	for i in range(n - k - 1):
		c -= b[i]
		c += b[i + k]
		if c == k:
			r += 1
	print(r)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	ans = [1] * n
	for i in range(1, n):
		if nums[i - 1] < 2 * nums[i]:
			ans[i] = 1 + ans[i - 1]
	count = 0
	for i in range(k, n):
		if ans[i] - ans[i - k] == k:
			count += 1
	print(count)


for x in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	sub = 0
	ans = [0] * n
	for x in range(n - 1):
		if l[x] < l[x + 1] * 2:
			ans[x] = 1
	s = 0
	for x in range(k):
		s += ans[x]
	if s == k:
		sub += 1
	for y in range(k, n - 1):
		s -= ans[y - k]
		s += ans[y]
		if s == k:
			sub += 1
	print(sub)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	r = []
	cnt = 0
	for i in range(n - 1):
		r.append(l[i] < 2 * l[i + 1])
	ones = sum(r[:k])
	if ones == k:
		cnt += 1
	for i in range(k, n - 1):
		ones += r[i]
		ones -= r[i - k]
		if ones == k:
			cnt += 1
	print(cnt)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [0] * (n - 1)
	for i in range(n - 1):
		b[i] = 1 if a[i] < 2 * a[i + 1] else 0
	ans = 0
	c = sum(b[:k])
	if c == k:
		ans += 1
	for i in range(n - k - 1):
		c -= b[i]
		c += b[i + k]
		if c == k:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	arr_bool = [True]
	for i in range(1, n):
		if arr[i - 1] < 2 * arr[i]:
			arr_bool.append(True)
		else:
			arr_bool.append(False)
	arr_bool.append(False)
	i = 0
	count = 0
	start = 0
	for (i, bool) in enumerate(arr_bool):
		if not bool:
			count += max(i - start - k, 0)
			start = i
	print(count)


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	cnt = 0
	for j in range(k):
		cnt += a[j] >= a[j + 1] * 2
	for i in range(n - k):
		ans += cnt == 0
		cnt -= a[i] >= a[i + 1] * 2
		if i + 1 + k < n:
			cnt += a[i + k] >= a[i + k + 1] * 2
	return ans
for _ in range(int(input())):
	print(solve())


def read_arr():
	return list(map(int, input().split(' ')))
_t = 1
_t = int(input())
for _i in range(_t):
	(n, k) = read_arr()
	A = read_arr()
	B = [0] * n
	(ans, cur) = (0, 0)
	for i in range(1, n):
		if A[i] * 2 > A[i - 1]:
			B[i] = 1
	for b in B:
		if b == 1:
			cur += 1
			if cur >= k:
				ans += 1
		else:
			cur = 0
	print(ans)


for _ in range(int(input())):
	(n, k) = input().split(' ')
	(n, k) = (int(n), int(k))
	arr = input().split(' ')
	k += 1
	temp = 1
	ans = 0
	for i in range(n):
		arr[i] = int(arr[i])
		if i != 0 and 2 * arr[i] > arr[i - 1]:
			temp += 1
		else:
			temp = 1
		ans += 1 if temp >= k else 0
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = [int(v) for v in input().split()]
	w = [int(v) for v in input().split()]
	z = []
	for j in range(1, n):
		if w[j] * 2 > w[j - 1]:
			z.append(1)
		else:
			z.append(0)
	res = 0
	c = 0
	for j in range(n - 1):
		if z[j] == 1:
			c += 1
		else:
			if c >= k:
				res += c - k + 1
			c = 0
	if c >= k:
		res += c - k + 1
	print(res)