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: interview

Starter code:

Solutions:
# cook your dish here
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=list(map(int,input().split()))
 a=list(map(int,input().split()))
 print(solution(a,n,d))


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))
 #print(arr)
 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')
   



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):
  #flag = 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')

 


# cook your dish here
# cook your dish here
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
    else:
     if(i==n-2):
     
      break
     else:
      if(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
     else:
      if(i==1):
       flag=1
       break
      else:
       if(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")

# cook your dish here
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")


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")

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 = list(map(int, input().split()))
 a = [int(e) for e in input().split()]
 startVal = a[0]
 a.sort()
 band = True
 startPos = 0
 #print(a)
 for i, e in enumerate(a[1: ]):
  #print("i: {}, e: {}, ant:{}".format(i,e,a[i]))
  if e - a[i] > d:
   band = False
   break
  if e == startVal:
   startPos = i + 1
 #print(band)
 if band and (check(a, startPos, d) or check2(a, startPos, d)):
  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")