Luke likes to eat. There are $n$ piles of food aligned in a straight line in front of him. The $i$-th pile contains $a_i$ units of food.

Luke will walk from the $1$-st pile towards the $n$-th pile, and he wants to eat every pile of food without walking back. When Luke reaches the $i$-th pile, he can eat that pile if and only if $|v - a_i| \leq x$, where $x$ is a fixed integer, and $v$ is Luke's food affinity.

Before Luke starts to walk, he can set $v$ to any integer. Also, for each $i$ ($1 \leq i \leq n$), Luke can change his food affinity to any integer before he eats the $i$-th pile.

Find the minimum number of changes needed to eat every pile of food.

Note that the initial choice for $v$ is not considered as a change.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases. The description of test cases follows.

For each test case, the first line contains two integers, $n, x$ ($1 \leq n \leq 2 \cdot 10^5$, $1 \leq x \leq 10^9$) — the number of piles, and the maximum difference between the size of a pile and Luke's food affinity, such that Luke can eat the pile.

The second line contains $n$ integers $a_1, a_2, \ldots , a_n$ ($1 \leq a_i \leq 10^9$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, output an integer on a separate line, which is the minimum number of changes needed.


-----Examples-----

Input
7
5 3
3 8 5 6 7
5 3
3 10 9 8 7
12 8
25 3 3 17 8 6 1 16 15 25 17 23
10 2
1 2 3 4 5 6 7 8 9 10
8 2
2 4 6 8 6 4 12 14
8 2
2 7 8 9 6 13 21 28
15 5
11 4 13 23 7 10 5 21 20 11 17 5 29 16 11
Output
0
1
2
1
2
4
6


-----Note-----

In the first test case, Luke can set $v$ to $5$ before he starts to walk. And he can walk straight to eat every piles of food without changing $v$.

In the second test case, Luke can set $v$ to $3$ before he starts to walk. And he could change $v$ to $10$ before he eats the second pile. After that, he can walk straight to eat remaining food without changing $v$.

In the fourth test case, Luke can set $v$ to $3$ before he starts to walk. And he could change $v$ to $8$ before he eats the sixth pile. After that, he can walk straight to eat remaining food without changing $v$.

In the fifth test case, Luke can set $v$ to $4$ before he starts to walk. And he could change $v$ to $6$ before he eats the fourth pile. Then he could change $v$ to $12$ before he eats the seventh pile. After that, he can walk straight to eat remaining food without changing $v$.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Implementation

Greedy algorithms


Solutions:
def main():
	t = int(input())
	for _ in range(t):
		(n, x) = [int(i) for i in input().split()]
		x *= 2
		a = [int(i) for i in input().split()]
		(min_cur, max_cur) = (a[0], a[0])
		res = 0
		for i in a:
			if i < min_cur:
				min_cur = i
			if i > max_cur:
				max_cur = i
			delta = max_cur - min_cur
			if delta > x:
				res += 1
				(min_cur, max_cur) = (i, i)
		print(res)
main()


t = int(input())
sol = []
for _ in range(t):
	(n, x) = [int(x) for x in input().split()]
	first = True
	count = 0
	nums = [int(x) for x in input().split()]
	mmin = nums[0]
	mmax = nums[0]
	for num in nums:
		if num > mmax:
			mmax = num
		if num < mmin:
			mmin = num
		if mmax - mmin > 2 * x:
			count += 1
			mmax = num
			mmin = num
	sol.append(count)
for s in sol:
	print(s)


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


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	g = x * 2 + 1
	a = b = l[0]
	ans = 0
	for y in l:
		if y < a:
			a = y
		if y > b:
			b = y
		if b - a >= g:
			ans += 1
			b = y
			a = y
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	max = l[0]
	min = l[0]
	for i in l[1:]:
		if i > max:
			max = i
		if i < min:
			min = i
		if max - min > 2 * x:
			c += 1
			max = min = i
	sys.stdout.write(str(c) + '\n')
	t -= 1


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	Food_Pile = [int(x) for x in input().split()]
	Cap = x * 2
	_max = Food_Pile[0]
	_min = Food_Pile[0]
	count = 0
	for size in Food_Pile:
		if size >= _max:
			_max = size
			if _max - _min > Cap:
				count += 1
				_min = size
		elif size < _min:
			_min = size
			if _max - _min > Cap:
				count += 1
				_max = size
	print(count)


trials = int(input())
answer_list = []
for _ in range(trials):
	i = input().split(' ')
	l = int(i[0])
	d = int(i[1])
	li = input().split(' ')
	ans = 0
	mini = int(li[0])
	maxi = int(li[0])
	for k in li:
		i = int(k)
		if i > maxi:
			maxi = i
		if i < mini:
			mini = i
		if maxi - mini > d * 2:
			maxi = i
			mini = i
			ans += 1
	answer_list.append(ans)
for g in answer_list:
	print(g)


import sys
t = int(input())
for _ in range(t):
	nm = [int(ii) for ii in input().split()]
	(n, x) = (nm[0], nm[1])
	mas = [int(ii) for ii in input().split()]
	(a, b) = (mas[0], mas[0])
	ans = 0
	for i in mas:
		if i < a:
			a = i
		elif i > b:
			b = i
		if b - a > 2 * x:
			ans += 1
			(a, b) = (i, i)
	print(ans)


def print_food_diff(n, x, arr):
	if n == 1:
		print(0)
		return
	count = 0
	maxi = arr[0]
	mini = arr[0]
	for i in range(1, n):
		if arr[i] > maxi:
			maxi = arr[i]
		if arr[i] < mini:
			mini = arr[i]
		if maxi - mini > 2 * x:
			count += 1
			maxi = arr[i]
			mini = arr[i]
	print(count)

def main():
	t = int(input())
	for i in range(t):
		(n, x) = map(int, input().split())
		arr = list(map(int, input().split()))
		print_food_diff(n, x, arr)
main()


import sys

def solve():
	inp = sys.stdin.readline
	(n, x) = map(int, inp().split())
	m = int(2000000000.0)
	M = int(-2000000000.0)
	x *= 2
	r = 0
	for v in map(int, inp().split()):
		mm = min(m, v)
		MM = max(M, v)
		if MM - mm > x:
			r += 1
			m = v
			M = v
		else:
			m = mm
			M = MM
	print(r)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


def main():
	for t in range(int(input())):
		(n, x) = map(int, input().split())
		a = list(map(int, input().split()))
		(mi, mx) = (271644049215, 0)
		ans = 0
		for i in range(n):
			if a[i] < mi:
				mi = a[i]
			if a[i] > mx:
				mx = a[i]
			if abs(mx - mi) > 2 * x:
				ans += 1
				(mx, mi) = (a[i], a[i])
		print(ans)
main()


def solve():
	(n, x) = map(int, input().split())
	ls = list(map(int, input().split()))
	ret = 0
	min_ = 10 ** 9
	max_ = -10 ** 9
	for i in range(n):
		if ls[i] < min_:
			min_ = ls[i]
		if ls[i] > max_:
			max_ = ls[i]
		if 2 * x < max_ - min_:
			max_ = ls[i]
			min_ = max_
			ret += 1
	print(ret)
t = int(input())
for i in range(t):
	solve()


t = int(input())
for _ in range(t):
	(n, x) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	k = 0
	(lo, hi) = (a[0], a[0])
	for y in a[1:]:
		if y > hi or y < lo:
			if y - lo > 2 * x or hi - y > 2 * x:
				(lo, hi) = (y, y)
				k += 1
			else:
				hi = max(hi, y)
				lo = min(lo, y)
	print(k)


def ss(a, n, k):
	i = 0
	count = 0
	(l, r) = (a[0], a[0])
	while i < n:
		if abs(r - l) > 2 * k:
			count += 1
			l = a[i - 1]
			r = a[i - 1]
		if a[i] < l:
			l = a[i]
		if a[i] > r:
			r = a[i]
		i += 1
	if abs(l - a[-1]) > 2 * k or abs(r - a[-1]) > 2 * k:
		count += 1
	return count
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(ss(a, n, k))


def solve(a, x):
	lim_sup = a[0] + x
	lim_inf = a[0] - x
	changes = 0
	for e in a:
		new_lim_sup = e + x
		new_lim_inf = e - x
		if lim_sup < new_lim_inf or new_lim_sup < lim_inf:
			changes += 1
			lim_sup = new_lim_sup
			lim_inf = new_lim_inf
		else:
			lim_sup = min(lim_sup, new_lim_sup)
			lim_inf = max(lim_inf, new_lim_inf)
	return changes
t = int(input())
for _ in range(t):
	(n, x) = [int(e) for e in input().split()]
	a = [int(e) for e in input().split()]
	print(solve(a, x))


def answer_finder():
	(number_of_piles, max_affinity_luke) = [int(val) for val in input().split()]
	input_array = [int(val) for val in input().split()]
	number_of_piles_array_handler = input_array[0] - max_affinity_luke
	max_affinity_luke_array_handler = input_array[0] + max_affinity_luke
	result_that_will_be_printed = 0
	for i in range(1, number_of_piles):
		if input_array[i] - max_affinity_luke > max_affinity_luke_array_handler or input_array[i] + max_affinity_luke < number_of_piles_array_handler:
			result_that_will_be_printed += 1
			number_of_piles_array_handler = input_array[i] - max_affinity_luke
			max_affinity_luke_array_handler = input_array[i] + max_affinity_luke
		else:
			if input_array[i] - max_affinity_luke > number_of_piles_array_handler:
				number_of_piles_array_handler = input_array[i] - max_affinity_luke
			if input_array[i] + max_affinity_luke < max_affinity_luke_array_handler:
				max_affinity_luke_array_handler = input_array[i] + max_affinity_luke
	print(result_that_will_be_printed)
test_cases = int(input())
while test_cases:
	test_cases -= 1
	answer_finder()


import sys
input = sys.stdin.readline

def solve():
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	mi = ma = arr[0]
	ans = 0
	for i in range(n):
		mi = min(mi, arr[i])
		ma = max(ma, arr[i])
		if ma - mi <= 2 * x:
			continue
		ans += 1
		ma = mi = arr[i]
	return ans
for _ in range(int(input())):
	print(solve())


from math import inf
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	maxM = -inf
	minM = inf
	c = 0
	for i in a:
		if i > maxM:
			maxM = i
		if i < minM:
			minM = i
		if maxM - minM > 2 * x:
			c += 1
			minM = i
			maxM = i
	print(c)


def ss(l, x):
	ans = 0
	mx = l[0]
	mn = l[0]
	for i in l:
		mx = max(mx, i)
		mn = min(mn, i)
		if mx - mn > 2 * x:
			ans += 1
			mx = i
			mn = i
	return ans
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	print(ss(l, x))


def solve(x, A):
	cn = 0
	c_min = A[0] - x
	c_max = A[0] + x
	for v in A:
		min_v = v - x
		max_v = v + x
		if c_max < min_v or c_min > max_v:
			cn += 1
			c_min = min_v
			c_max = max_v
		else:
			c_min = max(c_min, min_v)
			c_max = min(c_max, max_v)
	return cn

def read():
	s = input().strip('\n').split(' ')
	(n, x) = (int(s[0]), int(s[1]))
	s = input().strip('\n').split(' ')
	A = [int(x) for x in s]
	return (x, A)

def main():
	n = int(input())
	for _ in range(n):
		(x, A) = read()
		res = solve(x, A)
		print(res)
		pass
	pass
main()


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	m1 = a[0] - x
	m2 = a[0] + x
	q = 0
	for i in range(1, n):
		if a[i] + x < m1 or a[i] - x > m2:
			q += 1
			m1 = a[i] - x
			m2 = a[i] + x
		else:
			if a[i] + x < m2:
				m2 = a[i] + x
			if a[i] - x > m1:
				m1 = a[i] - x
	print(q)


def solve():
	(n, x) = map(int, input().split(' '))
	lst = list(map(int, input().split(' ')))
	mx = lst[0]
	mn = lst[0]
	ans = 0
	for i in lst:
		(mx, mn) = (max(i, mx), min(i, mn))
		if mx - mn > 2 * x:
			ans += 1
			(mx, mn) = (i, i)
	print(ans)
t = int(input())
while t:
	t -= 1
	solve()


T = int(input())
while T > 0:
	T -= 1
	S = input().split()
	a = [int(x) for x in S]
	n = a[0]
	m = a[1]
	S = input().split()
	a = [int(x) for x in S]
	minx = a[0]
	maxx = a[0]
	ans = 0
	for x in a:
		if minx > x:
			minx = x
		if maxx < x:
			maxx = x
		if maxx - minx > m + m:
			ans += 1
			maxx = x
			minx = x
	print(ans)


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
t = num_inp()
for _ in range(t):
	(n, x) = sp_inp()
	l = arr_inp()
	count = 0
	min = l[0]
	max = l[0]
	for i in range(1, n):
		if l[i] > max:
			max = l[i]
		elif l[i] < min:
			min = l[i]
		if max - min > 2 * x:
			count += 1
			max = l[i]
			min = l[i]
	print(count)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	c = 0
	maxi = l[0]
	mini = l[0]
	for i in l[1:]:
		if i > maxi:
			maxi = i
		if i < mini:
			mini = i
		if maxi - x > mini + x:
			c += 1
			maxi = mini = i
	print(c)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = list(map(int, input().split()))
	diff = 2 * k
	num_max = z[0]
	num_min = z[0]
	count = 0
	if max(z) - min(z) <= diff:
		print(0)
	else:
		for i in range(len(z)):
			if z[i] > num_max:
				num_max = z[i]
			if z[i] < num_min:
				num_min = z[i]
			if num_max - num_min > diff:
				count += 1
				num_min = num_max = z[i]
		print(count)


test_cases = int(input())

def handle():
	(n, x) = input().split(' ')
	n = int(n)
	x = int(x)
	food_piles = [int(s) for s in input().split(' ')]
	changes = 0
	min_so_far = food_piles[0]
	max_so_far = food_piles[0]
	for i in range(1, len(food_piles)):
		value = food_piles[i]
		min_so_far = min(min_so_far, value)
		max_so_far = max(max_so_far, value)
		if max_so_far - (min_so_far + x) > x:
			changes += 1
			min_so_far = value
			max_so_far = value
	return changes
for _ in range(test_cases):
	print(handle())


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	L = list(map(int, input().split()))
	mi = L[0]
	ma = L[0]
	i = 1
	ans = 0
	while i < n:
		a = L[i]
		if a > ma:
			if a - mi <= 2 * x:
				mi = min(a, mi)
				ma = max(ma, a)
			else:
				ans += 1
				mi = a
				ma = a
		elif a < mi:
			if ma - a <= 2 * x:
				mi = min(a, mi)
				ma = max(ma, a)
			else:
				ans += 1
				mi = a
				ma = a
		else:
			pass
		i += 1
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	count = 0
	l = arr[0]
	h = arr[0]
	for i in range(n):
		if arr[i] < l:
			l = arr[i]
		if arr[i] > h:
			h = arr[i]
		if h - l > 2 * x:
			count += 1
			if i < n - 1:
				l = arr[i]
				h = arr[i]
	print(count)


from typing import List
from collections import defaultdict
from collections import deque

class Solution:

	def solve(self, n, x, a):
		count = 0
		(li, hi) = (a[0] - x, a[0] + x)
		for j in range(1, n):
			(lj, hj) = (a[j] - x, a[j] + x)
			if hj < li or hi < lj:
				count += 1
				(li, hi) = (lj, hj)
			else:
				li = max(li, lj)
				hi = min(hi, hj)
		return count
obj = Solution()
T = int(input())
for _ in range(T):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = obj.solve(n, x, a)
	print(ans)


t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mi = float('inf')
	ma = float('-inf')
	ans = 0
	for i in range(n):
		if a[i] > ma:
			ma = a[i]
		if a[i] < mi:
			mi = a[i]
		if ma - mi > 2 * x:
			ans += 1
			mi = a[i]
			ma = a[i]
	print(ans)
	t = t - 1


import sys
t = int(input())
while t:
	(p, q) = map(int, input().split())
	s = list(map(int, input().split()))
	check = 0
	(m, n) = (sys.maxsize, -sys.maxsize - 1)
	d = 0
	while d < p:
		if s[d] > n:
			n = s[d]
		if s[d] < m:
			m = s[d]
		if n - m > 2 * q:
			check += 1
			(m, n) = (s[d], s[d])
		d += 1
	print(check)
	t -= 1


for i in range(int(input())):
	(a, b) = input().split(' ')
	n = int(a)
	x = int(b)
	numbers = [int(x) for x in input().split(' ')]
	change = 0
	if n > 1:
		i = 1
		smaller = numbers[0]
		bigger = numbers[0]
		while i <= n - 1:
			if numbers[i] > bigger:
				bigger = numbers[i]
			if numbers[i] < smaller:
				smaller = numbers[i]
			if bigger - smaller > 2 * x:
				change += 1
				smaller = numbers[i]
				bigger = numbers[i]
			i += 1
	print(change)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	maxi = mini = a[0]
	c = 0
	for i in range(1, n):
		maxi = a[i] if a[i] > maxi else maxi
		mini = a[i] if a[i] < mini else mini
		if maxi - mini > 2 * x:
			maxi = mini = a[i]
			c += 1
	print(c)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	lis = list(map(int, input().split()))
	l = lis[0]
	r = lis[0]
	ans = 0
	for i in range(1, n):
		if lis[i] < l:
			l = lis[i]
		if lis[i] > r:
			r = lis[i]
		if r - l > 2 * x:
			ans += 1
			l = lis[i]
			r = lis[i]
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	s = 0
	x *= 2
	mx = a[0]
	mn = a[0]
	for i in range(1, n):
		if a[i] > mx:
			mx = a[i]
		if a[i] < mn:
			mn = a[i]
		d = mx - mn
		if d > x:
			s += 1
			mx = a[i]
			mn = a[i]
	print(s)


for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = 0
	max_v = a[0]
	min_v = a[0]
	for i in range(1, n):
		if a[i] > max_v:
			max_v = a[i]
		if a[i] < min_v:
			min_v = a[i]
		if max_v - min_v > 2 * x:
			max_v = a[i]
			min_v = a[i]
			ans += 1
	print(ans)


q = int(input())
for tc in range(q):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mina = a[0]
	maxa = a[0]
	ans = 0
	for i in range(1, n):
		if a[i] > maxa:
			maxa = a[i]
		if a[i] < mina:
			mina = a[i]
		if maxa - mina > 2 * x:
			ans += 1
			mina = maxa = a[i]
	print(ans)


case = int(input())
for i in range(case):
	(n, x) = (int(v) for v in input().split())
	a = [int(v) for v in input().split()]
	tmax = a[0]
	tmin = a[0]
	ans = 0
	for j in range(1, n):
		if a[j] > tmax:
			tmax = a[j]
		elif a[j] < tmin:
			tmin = a[j]
		else:
			pass
		if tmax - tmin > 2 * x:
			ans += 1
			tmax = a[j]
			tmin = a[j]
	print(ans)


n = int(input())
for _ in range(n):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	count = 0
	mina = a[0]
	maxa = a[0]
	for ai in a:
		mina = min(mina, ai)
		maxa = max(maxa, ai)
		if maxa - mina > 2 * x:
			count += 1
			mina = ai
			maxa = ai
	print(count)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	ans = 0
	ai = list(map(int, input().split()))
	curmax = curlow = ai[0]
	for i in range(1, n):
		if ai[i] > curmax:
			curmax = ai[i]
		if ai[i] < curlow:
			curlow = ai[i]
		if abs(curmax - curlow) > 2 * x:
			curmax = curlow = ai[i]
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mn = a[0] - x
	mx = a[0] + x
	ans = 0
	for i in range(1, n):
		if a[i] - x > mx or a[i] + x < mn:
			ans += 1
			mn = a[i] - x
			mx = a[i] + x
		elif a[i] - x > mn:
			mn = a[i] - x
		elif a[i] + x < mx:
			mx = a[i] + x
	print(ans)


for pratyush in range(int(input())):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	(h, t, f) = (a[0] - x, a[0] + x, 0)
	for i in range(1, n):
		if a[i] - x > t or a[i] + x < h:
			f += 1
			(h, t) = (a[i] - x, a[i] + x)
		else:
			if a[i] - x > h:
				h = a[i] - x
			if a[i] + x < t:
				t = a[i] + x
	print(f)


for _ in ' ' * int(input()):
	(n, x) = map(int, input().split())
	ans = 0
	ai = list(map(int, input().split()))
	max_ = low_ = ai[0]
	for i in range(1, n):
		if ai[i] > max_:
			max_ = ai[i]
		if ai[i] < low_:
			low_ = ai[i]
		if abs(max_ - low_) > 2 * x:
			max_ = low_ = ai[i]
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	nm = arr[0]
	nm1 = arr[0]
	res = 0
	for i in range(1, n):
		if arr[i] > nm1:
			nm1 = arr[i]
		if arr[i] < nm:
			nm = arr[i]
		if nm1 - nm > 2 * x:
			res += 1
			nm = nm1 = arr[i]
	print(res)


def solve():
	(n, x) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	diff = []
	mini = arr[0]
	maxi = arr[0]
	count = 0
	for i in range(len(arr)):
		mini = min(mini, arr[i])
		maxi = max(maxi, arr[i])
		if maxi - mini > 2 * x:
			mini = arr[i]
			maxi = arr[i]
			count += 1
	print(count)
t = int(input())
while t:
	t -= 1
	solve()


p = int(input())
for i in range(p):
	(n, m) = map(int, input().split())
	v = list(map(int, input().split()))
	q = 0
	x = v[0] - m
	y = v[0] + m
	for j in range(1, n):
		r = v[j] - m
		s = v[j] + m
		if x > s or y < r:
			q += 1
			x = r
			y = s
		else:
			if r > x:
				x = r
			if s < y:
				y = s
	print(q)


R = lambda : map(int, input().split())
(t,) = R()
while t:
	t -= 1
	(n, x) = R()
	m = 2000000000.0
	M = r = 0
	for y in R():
		if (M := max(M, y)) - (m := min(m, y)) > 2 * x:
			r += 1
			m = M = y
	print(r)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	poc = a[0]
	x *= 2
	gore = x
	dole = x
	b = 0
	for i in range(1, n):
		if a[i] >= poc and a[i] - poc <= gore:
			dole = min(dole, x - (a[i] - poc))
		elif a[i] < poc and poc - a[i] <= dole:
			gore = min(gore, x - (poc - a[i]))
		else:
			b += 1
			gore = x
			dole = x
			poc = a[i]
	print(b)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	_min = arr[0]
	_max = arr[0]
	x = 2 * x
	cnt = 0
	for a in arr[1:]:
		_min = min(a, _min)
		_max = max(a, _max)
		if _max - _min > x:
			_min = a
			_max = a
			cnt += 1
	print(cnt)


for _ in range(int(input())):
	(n, x) = map(int, input().split(' '))
	array = tuple(map(int, input().split(' ')))
	(start, end) = (array[0] - x, array[0] + x)
	result = 0
	for num in array[1:]:
		(c, d) = (num - x, num + x)
		if c <= start <= d and c <= end <= d:
			pass
		elif start <= c <= end and start <= d <= end:
			(start, end) = (c, d)
		elif start <= c <= end:
			start = c
		elif start <= d <= end:
			end = d
		else:
			result += 1
			(start, end) = (c, d)
	print(result)


import sys

def solve(n, k):
	l = [int(i) for i in sys.stdin.readline().split()]
	tot = 0
	(mx, mn) = (l[0], l[0])
	for i in range(1, n):
		mx = max(l[i], mx)
		mn = min(mn, l[i])
		if mx - mn > 2 * k:
			(mx, mn) = (l[i], l[i])
			tot += 1
	return tot
for i in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	print(solve(n, k))


t = int(input())
for i in range(t):
	(n, x) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	flag = 0
	maxa = a[0]
	mina = a[0]
	for ai in a[1:]:
		maxa = max(maxa, ai)
		mina = min(mina, ai)
		if maxa - mina > 2 * x:
			flag += 1
			maxa = ai
			mina = ai
	print(flag)


z = lambda : map(int, input().split())
(t,) = z()
for i in '_' * t:
	(n, x) = z()
	a = z()
	cnt = 0
	mn = 10 ** 10
	mx = 0
	for i in a:
		if (mx := max(mx, i)) - (mn := min(i, mn)) > 2 * x:
			cnt += 1
			mx = mn = i
	print(cnt)


reps = int(input())
for _ in range(reps):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	(maxi, mini) = (arr[0], arr[0])
	ans = 0
	for num in arr:
		maxi = max(num, maxi)
		mini = min(mini, num)
		if maxi - mini > 2 * x:
			ans += 1
			maxi = mini = num
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mini = a[0]
	maxi = a[0]
	res = 0
	for i in a:
		mini = min(mini, i)
		maxi = max(maxi, i)
		if maxi - mini > 2 * x:
			res += 1
			maxi = i
			mini = i
	print(res)


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


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	(_min, _max) = (a[0], a[0])
	count = 0
	x = 2 * x
	for i in a[1:]:
		_min = min(_min, i)
		_max = max(_max, i)
		if _max - _min > x:
			_max = i
			_min = i
			count += 1
	print(count)


a = int(input())
for _ in range(a):
	(pile, fix) = [int(x) for x in input().split()]
	ppile = [int(x) for x in input().split()]
	minx = -1
	maxx = -1
	count = 0
	for i in range(pile):
		if minx == -1 or ppile[i] < minx:
			minx = ppile[i]
		if maxx == -1 or ppile[i] > maxx:
			maxx = ppile[i]
		if maxx - minx > 2 * fix:
			count += 1
			minx = ppile[i]
			maxx = ppile[i]
	print(count)


un = lambda : [*map(int, input().split())]
for _ in range(*un()):
	(n, x) = un()
	a = un()
	minn = a[0]
	maxx = a[0]
	caunt = 0
	for i in range(1, n):
		j = 0
		if a[i] > maxx:
			maxx = a[i]
			j = 1
		if a[i] < minn:
			minn = a[i]
			j = 1
		if j == 1:
			if maxx - minn > 2 * x:
				caunt += 1
				(maxx, minn) = (a[i], a[i])
	print(caunt)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 0
	mi = 10 ** 9
	ma = 0
	for i in a:
		mi = min(i, mi)
		ma = max(i, ma)
		if ma - mi > 2 * x:
			c += 1
			ma = i
			mi = i
	print(c)


for _ in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	(maxlim, minlim) = (arr[0], arr[0])
	ans = 0
	for num in arr:
		maxlim = max(num, maxlim)
		minlim = min(num, minlim)
		if maxlim - minlim > 2 * x:
			ans += 1
			(maxlim, minlim) = (num, num)
	print(ans)


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, x) = map(int, sys.stdin.readline().split())
	lst = list(map(int, sys.stdin.readline().split()))
	ans = 0
	ele = lst[0]
	l = ele - x
	r = ele + x
	for j in lst[1:]:
		st = j - x
		en = j + x
		if st <= r and en >= l:
			l = max(l, st)
			r = min(r, en)
		else:
			ans += 1
			l = st
			r = en
	print(ans)


t = int(input())
for ncase in range(1, t + 1):
	(n, x) = [int(s) for s in input().split(' ')]
	a = [int(s) for s in input().split(' ')]
	ans = 0
	(m0, m1) = (a[0] - x, a[0] + x)
	for i in range(1, n):
		if a[i] + x < m0 or a[i] - x > m1:
			ans += 1
			(m0, m1) = (a[i] - x, a[i] + x)
		elif a[i] - x > m0:
			m0 = a[i] - x
		elif a[i] + x < m1:
			m1 = a[i] + x
	print(ans)


for _ in range(int(input())):
	(n, x) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	ans = 0
	mn = arr[0]
	mx = arr[0]
	for i in arr:
		mn = min(i, mn)
		mx = max(i, mx)
		if abs(mn - mx) > 2 * x:
			ans += 1
			mn = i
			mx = i
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	lst = list(map(int, input().split()))
	(mini, maxi) = (lst[0], lst[0])
	count = 0
	for i in lst[1:]:
		mini = min(mini, i)
		maxi = max(maxi, i)
		if maxi - mini > 2 * x:
			count += 1
			mini = i
			maxi = i
	print(count)


x = int(input())

def cal(n, m, arr):
	if n == 1:
		return 0
	(a, b) = (max(arr[0] - m, 0), arr[0] + m)
	ans = 0
	for i in range(1, n):
		(c, d) = (max(arr[i] - m, 0), arr[i] + m)
		if b < c or a > d:
			ans += 1
			(a, b) = (c, d)
		else:
			(a, b) = (max(a, c), min(b, d))
	return ans
for jj in range(x):
	(n, m) = [int(i) for i in input().split(' ')]
	arr = [int(i) for i in input().split(' ')]
	print(cal(n, m, arr))


for _ in range(int(input())):
	x = int(input().split()[1])
	a = list(map(int, input().split()))
	n = 0
	min_ = a[0]
	max_ = a[0]
	for i in a:
		min_ = min(i, min_)
		max_ = max(i, max_)
		if max_ - min_ > 2 * x:
			n += 1
			min_ = i
			max_ = i
	print(n)


t = int(input())

def gen_sol(n, x, a):
	ls_min = [-x + a_i for a_i in a]
	ls_max = [x + a_i for a_i in a]
	l_intr = -10 ** 12
	u_intr = 10 ** 12
	cnt = 0
	for i in range(n):
		(nl, nu) = (max(l_intr, ls_min[i]), min(u_intr, ls_max[i]))
		if nl <= nu:
			l_intr = nl
			u_intr = nu
		else:
			cnt += 1
			l_intr = ls_min[i]
			u_intr = ls_max[i]
	return cnt
for _ in range(t):
	(n, x) = [int(y) for y in input().split()]
	a = [int(y) for y in input().split()]
	print(gen_sol(n, x, a))


t = int(input())
for _ in range(t):
	(n, x) = list(map(int, input().split(' ')))
	arr = list(map(int, input().split(' ')))
	tmp = 0
	_min = float('inf')
	_max = float('-inf')
	for i in arr:
		_min = min(_min, i)
		_max = max(_max, i)
		if _max - _min > 2 * x:
			tmp += 1
			_min = i
			_max = i
	print(tmp)


t = int(input())
for i in range(0, t):
	(n, x) = map(int, input().split())
	a = input().split()
	c = []
	for j in a:
		c.append(int(j))
	a = c
	mi = a[0]
	ma = a[0]
	ans = 0
	for k in range(1, len(a)):
		if a[k] < mi:
			mi = a[k]
		elif a[k] > ma:
			ma = a[k]
		if ma - mi > 2 * x:
			ma = a[k]
			mi = a[k]
			ans = ans + 1
	print(ans)


cas = int(input())
for i in range(cas):
	(n, x) = [int(y) for y in input().split()]
	a = [int(y) for y in input().split()]
	c = 0
	mi = a[0]
	ma = a[0]
	for i in a:
		mi = min(i, mi)
		ma = max(i, ma)
		if ma - mi > 2 * x:
			c += 1
			ma = i
			mi = i
	print(c)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	myList = list(map(int, input().split()))
	small = big = myList[0]
	counter = 0
	for i in myList:
		small = min(i, small)
		big = max(i, big)
		if big - small > 2 * x:
			counter += 1
			big = small = i
	print(counter)


import math
import os
import random
import re
import sys
from math import gcd
from math import sqrt
from collections import Counter
from itertools import compress
from collections import deque
import statistics
from statistics import mode
for _ in range(int(input())):
	(n, x) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	mx = arr[0]
	mn = arr[0]
	count = 0
	for i in arr:
		mx = max(mx, i)
		mn = min(mn, i)
		if mx - mn > x * 2:
			count += 1
			mx = i
			mn = i
	print(count)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	s = [int(x) for x in input().split()]
	max0 = s[0]
	min0 = s[0]
	ans = 0
	for i in s:
		max0 = max(max0, i)
		min0 = min(min0, i)
		if max0 - min0 > 2 * x:
			ans += 1
			max0 = i
			min0 = i
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	food_list = list(map(int, input().split()))
	ans = 0
	(mn, mx) = (food_list[0], food_list[0])
	for j in food_list:
		mn = min(mn, j)
		mx = max(mx, j)
		if mx - mn > 2 * x:
			ans += 1
			(mx, mn) = (j, j)
	print(ans)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	(mn, mx) = (a[0], a[0])
	for i in range(n):
		mn = min(mn, a[i])
		mx = max(mx, a[i])
		if mx - mn > 2 * x:
			ans += 1
			(mn, mx) = (a[i], a[i])
	print(ans)


hm = int(input())
for _ in range(hm):
	c = 0
	helper = list(map(int, input().split(' ')))
	x = helper[1]
	eda = list(map(int, input().split(' ')))
	nabor = []
	ma = eda[0]
	mi = eda[0]
	nabor.append(eda[0])
	for i in range(1, len(eda)):
		if eda[i] > ma:
			if abs(eda[i] - mi) > x * 2:
				c += 1
				nabor.clear()
				ma = eda[i]
				mi = eda[i]
			else:
				ma = eda[i]
		elif eda[i] < mi:
			if abs(ma - eda[i]) > x * 2:
				c += 1
				nabor.clear()
				ma = eda[i]
				mi = eda[i]
			else:
				mi = eda[i]
		nabor.append(eda[i])
	print(c)


for _ in range(int(input())):
	(n, x) = [int(x) for x in input().split()]
	if 85557448454 == 'dnfuhru':
		print('Tanmay')
	ans = 0
	a = [int(x) for x in input().split()]
	mini = 10000000034000000000
	maxi = -99999999944549999999999
	for i in a:
		mini = min(mini, i)
		maxi = max(maxi, i)
		if 2 * x < maxi - mini:
			ans += 1
			maxi = mini = i
	print(ans)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	a = l[0] + x
	b = l[0] - x
	ans = 0
	for i in range(1, n):
		if l[i] + x >= b and l[i] - x <= a:
			a = min(l[i] + x, a)
			b = max(l[i] - x, b)
		else:
			a = l[i] + x
			b = l[i] - x
			ans = ans + 1
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	sch = 0
	minn = a[-1]
	maxx = a[-1]
	tek = a[-1]
	for i in range(len(a) - 2, -1, -1):
		if a[i] < minn:
			minn = a[i]
		if a[i] > maxx:
			maxx = a[i]
		if abs(tek - a[i]) > x:
			if maxx - minn > 2 * x:
				sch += 1
				tek = a[i]
				minn = a[i]
				maxx = a[i]
				continue
			if tek - a[i] > 0:
				tek = a[i] + x
			else:
				tek = a[i] - x
	print(sch)


t = int(input())
for t1 in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	mini = maxi = l[0]
	count = 0
	for i in range(1, len(l)):
		maxi = max(maxi, l[i])
		mini = min(mini, l[i])
		if maxi - mini > 2 * x:
			maxi = mini = l[i]
			count += 1
	print(count)


import math
for _ in range(int(input())):
	(n, x) = input().split(' ')
	x = int(x)
	l = [int(i) for i in input().split(' ')]
	cnt = 0
	mm = [0, 10000000000000]
	for i in l:
		mm[0] = min(mm[0], i)
		mm[1] = max(mm[1], i)
		if mm[1] - mm[0] > 2 * x:
			cnt += 1
			mm = [i] * 2
	print(cnt - 1)


attemps = int(input())
rez_mass = []
for _ in range(attemps):
	(n, x) = map(int, input().split())
	dishes = list(map(int, input().split()))[:n]
	result = 0
	(max_dish, min_dish) = (dishes[0], dishes[0])
	for i in range(1, n):
		max_dish = max(max_dish, dishes[i])
		min_dish = min(min_dish, dishes[i])
		if max_dish - min_dish > x * 2:
			result += 1
			max_dish = min_dish = dishes[i]
	rez_mass.append(result)
print(*rez_mass, sep='\n')


for tc in range(int(input())):
	(n, x) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ans = 0
	l = r = a[0]
	for i in range(1, n):
		l = min(l, a[i])
		r = max(r, a[i])
		if r - l > 2 * x:
			l = r = a[i]
			ans += 1
	print(ans)


def sigma(a, b):
	if a > b:
		return 1
	if b < a:
		return -1
	else:
		return 0
for t in range(int(input())):
	(n, x) = map(int, input().split())
	L = list(map(int, input().split()))
	i = 0
	ans = 0
	while i < n:
		min = L[i]
		max = L[i]
		for j in range(i + 1, n):
			if L[j] > max:
				max = L[j]
			if L[j] < min:
				min = L[j]
			if max - min > 2 * x:
				i = j
				ans += 1
				break
		else:
			break
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	mx = a[0]
	mi = a[0]
	res = 0
	for i in range(1, n):
		mx = max(mx, a[i])
		mi = min(mi, a[i])
		if mx - mi <= 2 * x:
			continue
		else:
			res += 1
			mx = a[i]
			mi = a[i]
	print(res)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	if n == 1:
		print(0)
		continue
	l = a[0] - x
	r = a[0] + x
	cnt = 0
	for i in range(1, n):
		ll = a[i] - x
		rr = a[i] + x
		if ll <= r and rr >= l:
			l = max(ll, l)
			r = min(rr, r)
		else:
			cnt += 1
			l = ll
			r = rr
	print(cnt)