Chef is deriving weird ways to sort his array. Currently he is trying to sort his arrays in increasing order by reversing some of his subarrays.

To make it more challenging for himself, Chef decides that he can reverse only those subarrays that have sum of its elements at most X. Soon he notices that it might not be always possible to sort the array with this condition.

Can you help the Chef by telling him if the given array can be sorted by reversing subarrays with sum at most X.

More formally, for a given array A and an integer X, check whether the array can be sorted in increasing order by reversing some (possibly none) of the subarrays such that the sum of all elements of the subarray is at most X.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- The first line of each test case contains of two space-separated integers N and X denoting the length of the array and the maximum sum of subarrays that you can reverse.
- The second line contains N space-separated integers A_{1}, A_{2},..., A_{N} representing the initial array.

------ Output Format ------ 

For each test case, output \texttt{YES} if Chef can sort the array using a finite number of operations, else output \texttt{NO}. 

You may print each character of the string in uppercase or lowercase (for example, the strings \texttt{YeS}, \texttt{yEs}, \texttt{yes} and \texttt{YES} will all be treated as identical).

------ Constraints ------ 

$1 ≤ T ≤ 5\cdot 10^{4}$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 2\cdot 10^{9}$
$1 ≤ X ≤ 2\cdot 10^{9}$
- Sum of $N$ over all test cases does not exceeds $3\cdot 10^{5}$.

----- Sample Input 1 ------ 
3
4 1
1 2 3 4
4 1
2 1 3 4
5 7
3 2 2 3 3

----- Sample Output 1 ------ 
YES
NO
YES

----- explanation 1 ------ 
Test case $1$: The array is already sorted so we need not make any operations.

Test case $2$: There is no subarray with sum less than or equal to $1$ so we cannot sort the array.

Test case $3$: We can reverse the subarray $A[1, 3]$ which has a sum of $3+2+2=7$. Thus, the reversed subarray is $[2, 2, 3]$. The resulting array is $[2, 2, 3, 3, 3]$. The array is sorted in $1$ operation.

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
def rev_sorting(arr, x, N):
	(a, b) = (0, 'YES')
	for i in range(N):
		if a > arr[i] and a + arr[i] > x:
			b = 'NO'
		a = max(a, arr[i])
	return b
t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(rev_sorting(arr, x, n))


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	(mx, f) = (0, 1)
	for i in range(n):
		if mx > l[i] and mx + l[i] > x:
			f = 0
		mx = max(mx, l[i])
	if f == 0:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, X) = map(int, input().split())
	l = list(map(int, input().split()))
	(answer, i) = ('YES', 0)
	while i < n - 1:
		if l[i] > l[i + 1]:
			if l[i] + l[i + 1] > X:
				print('NO')
				break
			else:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
		i += 1
	else:
		print(answer)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	a = 0
	b = 1
	res = True
	while b < n:
		if l[a] <= l[b]:
			a = b
			b = b + 1
		elif l[a] > l[b]:
			s = l[a] + l[b]
			if s <= x:
				b = b + 1
			else:
				res = False
				break
	print('YES' if res else 'NO')


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 'YES'
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			if a[i] + a[i + 1] > x:
				ans = 'NO'
				break
			(a[i], a[i + 1]) = (a[i + 1], a[i])
	print(ans)


for _ in range(int(input())):
	st = input()
	lt = st.split(' ')
	n = int(lt[0])
	x = int(lt[-1])
	bl = True
	lt = [int(i) for i in input().split(' ')]
	for i in range(n - 1):
		if lt[i] > lt[i + 1]:
			if lt[i] + lt[i + 1] <= x:
				(lt[i], lt[i + 1]) = (lt[i + 1], lt[i])
			else:
				bl = False
				break
	if bl == True:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	arr = list(map(int, input().split()))
	ans = 'YES'
	for i in range(N - 1):
		if arr[i] > arr[i + 1]:
			temp = arr[i]
			arr[i] = arr[i + 1]
			arr[i + 1] = temp
			if arr[i] + arr[i + 1] > X:
				ans = 'NO'
				break
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	n_list = list(map(int, input().split()))
	mx = 0
	flag = True
	for i in range(n):
		if mx > n_list[i] and mx + n_list[i] > x:
			flag = False
		mx = max(mx, n_list[i])
	print('YES' if flag else 'NO')


t = int(input())
for ni in range(t):
	(n, x) = map(int, input().split())
	l = [int(i) for i in input().split()]
	s = 0
	for i in range(n - 1):
		if l[i] > l[i + 1]:
			if l[i + 1] + l[i] <= x:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
			else:
				s = 1
				print('NO')
				break
	if s == 0:
		print('YES')


t = int(input())
for p in range(t):
	(n, x) = map(int, input().split())
	a = [int(i) for i in input().split()]
	(i, j) = (0, 1)
	res = True
	while j < n:
		if a[i] <= a[j]:
			i = j
			j = j + 1
		elif a[i] > a[j]:
			sm = a[i] + a[j]
			if sm <= x:
				j += 1
			else:
				res = False
				break
	print('YES' if res else 'NO')


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	(ans, i) = ('YES', 0)
	while i < n - 1:
		if l[i] > l[i + 1]:
			if l[i] + l[i + 1] > x:
				ans = 'NO'
				break
			else:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
		i += 1
	print(ans)


t = int(input())
for t in range(t):
	(n, x) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	flag = 1
	i = 0
	while i < n - 1:
		if arr[i] > arr[i + 1]:
			if arr[i] + arr[i + 1] > x:
				flag = 0
				break
			else:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
		i = i + 1
	if flag == 1:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(n - 1):
		if l[i] > l[i + 1]:
			if l[i] + l[i + 1] <= x:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
			else:
				print('NO')
				break
	else:
		print('YES')


for i in range(int(input())):
	(N, X) = map(int, input().split())
	l = list(map(int, input().split()))
	B = True
	for j in range(N - 1):
		if l[j] > l[j + 1]:
			if l[j] + l[j + 1] <= X:
				a = l[j]
				b = l[j + 1]
				l[j + 1] = a
				l[j] = b
			else:
				B = False
				break
	if B == True:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	c = 1
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			if a[i] + a[i + 1] <= x:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
			else:
				c = 0
	if c:
		print('YES')
	else:
		print('NO')


def checker(n, x, arr):
	mx_v = 0
	mx_ar = []
	dic = {}
	for i in range(n):
		if arr[i] > mx_v:
			mx_v = arr[i]
		mx_ar.append(mx_v)
		dic[arr[i]] = i
	sarr = sorted(arr)
	rarr = list(reversed(arr))
	for i in range(n):
		if mx_ar[i] != arr[i]:
			v = arr[i]
			if mx_ar[i] + v > x:
				return 'NO'
	return 'YES'
t = int(input())
for _ in range(t):
	nx = list(map(int, input().split()))
	n = nx[0]
	x = nx[1]
	arr = list(map(int, input().split()))
	print(checker(n, x, arr))


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	(mx, ans) = (0, 'YES')
	for y in a:
		if mx > y and y + mx > x:
			ans = 'NO'
		mx = max(mx, y)
	print(ans)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	curr_maximum = 0
	ans = 'YES'
	for val in a:
		if val < curr_maximum and val + curr_maximum > x:
			ans = 'NO'
			break
		if val > curr_maximum:
			curr_maximum = val
	print(ans)


for t in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	p = 0
	c = 0
	for i in arr:
		if i < p:
			if i > x - p:
				c = 1
		else:
			p = i
	if c == 1:
		print('NO')
	else:
		print('YES')


def exe():
	max_lst = [arr[0]]
	maxi = arr[0]
	for i in range(1, n):
		if maxi < arr[i]:
			maxi = arr[i]
		max_lst.append(maxi)
	for i in range(n):
		if max_lst[i] == arr[i]:
			continue
		elif max_lst[i] + arr[i] > x:
			return 'NO'
	return 'YES'
for i in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(exe())


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	ans = 'YES'
	max_value = 0
	for it in l:
		if max_value > it and max_value + it > x:
			ans = 'NO'
			break
		max_value = max(max_value, it)
	print(ans)


T = int(input())
for _ in range(T):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	count = 0
	flag = 'YES'
	for i in A:
		if count > i and count + i > X:
			flag = 'NO'
			break
		count = max(count, i)
	print(flag)


for i in range(int(input())):
	(n, x) = map(int, input().split(' '))
	li = list(map(int, input().split(' ')))
	(count, flag) = (0, 'YES')
	for i in li:
		if count > i and count + i > x:
			flag = 'NO'
			break
		count = max(count, i)
	print(flag)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l1 = list(map(int, input().split()))
	count = 0
	ans = 'YES'
	for i in l1:
		if count > i and i + count > x:
			ans = 'NO'
			break
		count = max(i, count)
	print(ans)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split(' ')))
	ans = 'YES'
	mx = 0
	for i in a:
		if mx > i and i + mx > x:
			ans = 'NO'
			break
		mx = max(i, mx)
	print(ans)


from math import gcd, sqrt, ceil, floor, log10
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
sys.setrecursionlimit(3000000)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(1000000000.0) + 7
NEWLINE = '\n'
SPACE = ' '
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))

def solve(*args, **kwargs):
	(n, x, arr) = args
	max_ = arr[0]
	flag = True
	for i in range(n - 1):
		if max_ > arr[i + 1]:
			if max_ + arr[i + 1] > x:
				flag = False
				return 'NO'
		else:
			max_ = arr[i + 1]
	return 'YES' if flag else 'NO'

def main(*args, **kwargs):
	for _ in range(int(input())):
		(arg1, arg2) = inp_vars(int, SPACE)
		arg3 = inp_vars(int, SPACE)
		res = solve(*(arg1, arg2, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep=' ')
		else:
			print(res)
main()


for _ in range(int(input())):
	(N, X) = map(int, input().split())
	A = list(map(int, input().split()))
	mx = 0
	ans = 'YES'
	for a in A:
		if mx > a and a + mx > X:
			ans = 'NO'
			break
		mx = max(a, mx)
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	m = 0
	f = 0
	for i in range(n):
		if m > a[i] and m + a[i] > k:
			print('NO')
			f = 1
			break
		m = max(m, a[i])
	if f == 0:
		print('YES')


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	arr = list(map(int, input().split()))
	spam = 1
	for i in range(n - 1):
		summ = arr[i] + arr[i + 1]
		if arr[i] > arr[i + 1]:
			if summ > x:
				spam = 0
				break
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	if spam == 1:
		print('YES')
	else:
		print('NO')


from sys import stdin
for _ in range(int(stdin.readline())):
	(n, atmost) = map(int, stdin.readline().split())
	arr = list(map(int, stdin.readline().split()))
	status = 1
	for i in range(n - 1):
		total = arr[i] + arr[i + 1]
		if arr[i] > arr[i + 1]:
			if total > atmost:
				status = 0
				break
			(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	print('YES' if status else 'NO')


t = int(input())
while t > 0:
	(n, x) = input().split(' ')
	array = list(map(int, input().split(' ')[:int(n)]))
	if n == 1:
		print('YES')
	else:
		ans = 1
		currmax = array[0]
		for i in range(int(n)):
			if array[i] < currmax and array[i] + currmax > int(x):
				ans = 0
				break
			currmax = max(currmax, array[i])
		if ans == 0:
			print('NO')
		else:
			print('YES')
	t -= 1


t = int(input())
for j in range(t):
	(n, x) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	mx = 0
	fl = True
	for ele in arr:
		if ele < mx and mx + ele > x:
			fl = False
			break
		mx = max(ele, mx)
	if fl:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(0, t):
	flag = 0
	l = []
	(n, x) = [int(i) for i in input().split()]
	l = [int(i) for i in input().split()]
	for k in range(0, len(l) - 1):
		if l[k] > l[k + 1]:
			if l[k] + l[k + 1] > x:
				flag = 1
			else:
				temp = l[k]
				l[k] = l[k + 1]
				l[k + 1] = temp
		else:
			pass
	if flag == 1:
		print('NO')
	else:
		print('YES')


import copy
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l1 = list(map(int, input().split()))
	f = 1
	for i in range(n - 1):
		if l1[i] > l1[i + 1]:
			if l1[i] + l1[i + 1] > x:
				f = 0
				break
			else:
				(l1[i], l1[i + 1]) = (l1[i + 1], l1[i])
	if f == 0:
		print('NO')
	else:
		print('YES')


def sort(N, X, array):
	for k in range(N - 1):
		if array[k] > array[k + 1]:
			if array[k] + array[k + 1] > X:
				return 'NO'
			else:
				(array[k], array[k + 1]) = (array[k + 1], array[k])
	return 'YES'
T = int(input())
for t in range(T):
	(N, X) = [int(j) for j in input().split()]
	array = list(map(int, input().split()))
	print(sort(N, X, array))


def check(arr, a, p):
	for i in range(a - 1):
		if arr[i] > arr[i + 1]:
			if arr[i] + arr[i + 1] > p:
				return False
			else:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return True
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	A = list(map(int, input().split()))
	if check(A, n, x):
		print('YES')
	else:
		print('NO')


def fun(a, b, l):
	for i in range(a - 1):
		if l[i] > l[i + 1]:
			if l[i] + l[i + 1] > b:
				return 'NO'
			else:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
	return 'YES'
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	print(fun(a, b, l))


def checking(a, p, arr):
	for i in range(a - 1):
		if arr[i] > arr[i + 1]:
			if arr[i] + arr[i + 1] > p:
				return 'NO'
			else:
				(arr[i], arr[i + 1]) = (arr[i + 1], arr[i])
	return 'YES'
t = int(input())
for i in range(t):
	(n, s) = map(int, input().split())
	li = list(map(int, input().split()))
	st = checking(n, s, li)
	print(st)