Chef works in a similar way to a travelling salesman ― he always travels to new cities in order to sell his delicious dishes.
Today, Chef is planning to visit $N$ cities (numbered $1$ through $N$). There is a direct way to travel between each pair of cities. Each city has a specific temperature; let's denote the temperature in the $i$-th city by $C_i$. Chef has a fixed temperature tolerance $D$ with the following meaning: for each pair of cities $a$ and $b$, he may travel from city $a$ directly to city $b$ only if $|C_a-C_b| \le D$, otherwise he would catch a heavy flu because of the sudden change in temperature.
Chef starts from city $1$. Is he able to visit all $N$ cities in such a way that each city is visited exactly once?
Notes:
- Chef is not able to travel through a city without visiting it.
- City $1$ is visited at the beginning.
- It is not necessary to be able to travel directly to city $1$ from the last city Chef visits.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $D$.
- The second line contains $N$ space-separated integers $C_1, C_2, \ldots, C_N$.

-----Output-----
For each test case, print a single line containing the string "YES" (without quotes) if Chef can visit all cities or "NO" (without quotes) if he cannot.

-----Constraints-----
- $1 \le T \le 1,000$
- $2 \le N \le 10^5$
- $0 \le D \le 10^9$
- $0 \le C_i \le 10^9$ for each valid $i$
- the sum of $N$ over all test cases does not exceed $10^6$

-----Subtasks-----
Subtask #1 (20 points):
- $N \le 1,000$
- the sum of $N$ over all test cases does not exceed $10,000$
Subtask #2 (80 points): original constraints

-----Example Input-----
2
5 3
3 2 1 4 5
5 4
10 1 3 2 9

-----Example Output-----
YES
NO

Difficulty: VERY_HARD
Tags: Sorting

Constructive algorithms

Ad-hoc
Skill types: Sorting

Starter code:

Solutions:
def solution(b, n1, d):
	first = b[0]
	b.sort()
	for j in range(n1 - 1):
		if a[j + 1] - a[j] > d:
			return 'NO'
	for j in range(n1):
		if b[j] == first:
			pos = j
	if pos == 0 or pos == n1 - 1:
		return 'YES'
	rec = 1
	for j in range(pos - 1, n1 - 2):
		if a[j + 2] - a[j] > d:
			rec = 0
			break
	if rec:
		return 'YES'
	rec = 1
	for j in range(pos + 1, 1, -1):
		if a[j] - a[j - 2] > d:
			rec = 0
			break
	if rec:
		return 'YES'
	else:
		return 'NO'
testcase = int(input())
for i in range(testcase):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	print(solution(a, n, d))


def ch(a):
	for i in range(1, len(a)):
		if a[i] - a[i - 1] > d:
			return False
	return True
for i in range(int(input())):
	(n, d) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = a[0]
	a.sort()
	ind = a.index(b)
	i = ind
	if not ch(a):
		print('NO')
	else:
		arr1 = []
		arr2 = []
		arr3 = []
		arr4 = []
		i = 0
		uind = ind
		if ind != n - 1:
			uind += 1
		while i <= uind:
			arr1.append(a[i])
			if i + 1 <= uind:
				arr2.append(a[i + 1])
			i += 2
		if i:
			i = ind - 1
		while i < n:
			arr3.append(a[i])
			if i + 1 < n:
				arr4.append(a[i + 1])
			i += 2
		if ch(arr1) and ch(arr2) or (ch(arr3) and ch(arr4)):
			print('YES')
		else:
			print('NO')


t = int(input())
for _ in range(t):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	v = {i: 0 for i in a}
	v[a[0]] = 1
	x = a[0]
	poss = 1
	(poss2, poss3) = (True, True)
	a.sort()
	for i in range(n - 1):
		if a[i + 1] - a[i] > d:
			poss = 0
			break
	if poss:
		st = a.index(x)
		if st != n - 1 and st != 0 and poss:
			for i in range(st):
				if a[i + 2] - a[i] > d:
					poss2 = False
					break
			if poss2 == False:
				for i in range(st - 1, n - 2):
					if a[i + 2] - a[i] > d:
						poss3 = False
						break
	if (poss2 or poss3) and poss:
		print('YES')
	else:
		print('NO')


def check(a, pos, d):
	if pos == 0 or pos == len(a) - 1:
		return True
	for i in range(pos + 1, len(a)):
		if a[i] - a[i - 2] > d:
			return False
	return True

def check2(a, pos, d):
	for i in range(pos - 1, -1, -1):
		if a[i + 2] - a[i] > d:
			return False
	return True
T = int(input())
for _ in range(T):
	(n, d) = map(int, input().split())
	a = [int(e) for e in input().split()]
	startVal = a[0]
	a.sort()
	band = True
	startPos = 0
	for (i, e) in enumerate(a[1:]):
		if e - a[i] > d:
			band = False
			break
		if e == startVal:
			startPos = i + 1
	if band and (check(a, startPos, d) or check2(a, startPos, d)):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(0, T):
	(N, D) = list(map(int, input().split()))
	s = [int(x) for x in input().split()]
	L = []
	for j in range(0, len(s)):
		L.append(j)
	arr = sorted(zip(s, L))
	ptr = -1
	for j in range(0, len(arr)):
		if arr[j][1] == 0:
			ptr = j
			break
	if N == 1:
		print('YES')
	else:
		temp1 = 0
		temp2 = 0
		temp = 0
		for j in range(0, len(arr) - 1):
			if abs(arr[j][0] - arr[j + 1][0]) > D:
				temp = 1
				break
		if ptr != 0 and ptr != len(arr) - 1:
			for j in range(0, ptr):
				if abs(arr[j][0] - arr[j + 2][0]) > D:
					temp1 = 1
					break
			if temp1 == 1:
				for j in range(ptr - 1, len(arr) - 2):
					if abs(arr[j][0] - arr[j + 2][0]) > D:
						temp2 = 1
						break
		if temp == 0 and (temp1 == 0 or temp2 == 0):
			print('YES')
		else:
			print('NO')


def left(a, pos):
	if pos == 0 or pos == len(a) - 1:
		return True
	for i in range(pos + 1, len(a)):
		if a[i] - a[i - 2] > d:
			return False
	return True

def right(a, pos):
	for i in range(pos - 1, -1, -1):
		if a[i + 2] - a[i] > d:
			return False
	return True
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	a = list(map(int, input().split()))
	startVal = a[0]
	a.sort()
	f = 1
	startPos = 0
	for (i, e) in enumerate(a[1:]):
		if e - a[i] > d:
			f = 0
			break
		if e == startVal:
			startPos = i + 1
	if f and (left(a, startPos) or right(a, startPos)):
		print('YES')
	else:
		print('NO')


tests = int(input())
for te in range(tests):
	(n, d) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	c = arr[0]
	arr.sort()
	for i in range(n):
		if arr[i] == c:
			index = i
	flag = 0
	for i in range(1, n):
		if abs(arr[i] - arr[i - 1]) > d:
			print('NO')
			flag = 1
			break
	if flag == 1:
		continue
	if index == 0 or index == n - 1:
		print('YES')
		continue
	for i in range(index + 1, n):
		if abs(arr[i] - arr[i - 2]) > d:
			flag = 1
			break
	if flag == 0:
		print('YES')
		continue
	flag = 0
	for i in range(index - 1, -1, -1):
		if abs(arr[i] - arr[i + 2]) > d:
			flag = 1
			break
	if flag == 0:
		print('YES')
		continue
	else:
		print('NO')


for _ in range(int(input())):
	(n, d) = map(int, input().split())
	li = list(map(int, input().split()))
	ini = li[0]
	li.sort()
	tvl = 1
	nidx = li.index(ini)
	for i in range(n - 1):
		if li[i + 1] - li[i] > d:
			tvl = 0
			break
	flag = 0
	if tvl:
		if nidx != 0 or nidx != n - 1:
			i = nidx
			while i < n - 1:
				if li[i + 1] - li[i - 1] > d:
					tvl = 0
					break
				elif i == n - 2:
					break
				elif li[i + 2] - li[i] <= d:
					i += 2
				else:
					tvl = 0
					break
			if not tvl:
				i = nidx
				while i > 0:
					if li[i + 1] - li[i - 1] > d:
						tvl = 0
						break
					elif i == 1:
						flag = 1
						break
					elif li[i] - li[i - 2] <= d:
						i -= 2
					else:
						tvl = 0
						break
				if i == 1 and flag or i == 0:
					tvl = 1
	if tvl == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, d) = [int(i) for i in input().split()]
	checkright2 = True
	checkleft2 = True
	check1 = True
	c = [int(i) for i in input().split()]
	startpoint = c[0]
	c.sort()
	for i in range(n - 1):
		if c[i + 1] - c[i] > d:
			check1 = False
			break
	startindex = c.index(startpoint)
	if startindex != n - 1 and startindex != 0 and check1:
		for i in range(startindex):
			if c[i + 2] - c[i] > d:
				checkleft2 = False
				break
		if checkleft2 == False:
			for i in range(startindex - 1, n - 2):
				if c[i + 2] - c[i] > d:
					checkright2 = False
					break
	if (checkright2 or checkleft2) and check1:
		print('YES')
	else:
		print('NO')


def check_1(s, d):
	for i in range(len(s) - 1):
		if s[i + 1] - s[i] > d:
			return False
	return True

def left1(s, index, d):
	for i in range(index - 1):
		if s[i + 1] - s[i] > d:
			return False
	return True

def right1(s, index, d):
	for i in range(index + 1, len(s) - 1):
		if s[i + 1] - s[i] > d:
			return False
	return True

def left2(s, index, d):
	for i in range(index - 1):
		if s[i + 2] - s[i] > d:
			return False
	return True

def right2(s, index, d):
	for i in range(index, len(s) - 2):
		if s[i + 2] - s[i] > d:
			return False
	return True
for _ in range(int(input())):
	(n, d) = map(int, input().split())
	s = [int(i) for i in input().split()]
	start = s[0]
	flag = False
	s.sort()
	if start in [min(s), max(s)]:
		if check_1(s, d):
			print('YES')
		else:
			print('NO')
	else:
		index = s.index(start)
		if left1(s, index, d) and right2(s, index, d) and (s[index + 1] - s[index - 1] <= d) and (s[-1] - s[-2] <= d) or (left2(s, index, d) and right1(s, index, d) and (s[index + 1] - s[index - 1] <= d) and (s[1] - s[0] <= d)):
			print('YES')
		else:
			print('NO')