You have an array $a$ of length $n$. You can exactly once select an integer $len$ between $1$ and $n - 1$ inclusively, and then sort in non-decreasing order the prefix of the array of length $len$ and the suffix of the array of length $n - len$ independently.

For example, if the array is $a = [3, 1, 4, 5, 2]$, and you choose $len = 2$, then after that the array will be equal to $[1, 3, 2, 4, 5]$.

Could it be that after performing this operation, the array will not be sorted in non-decreasing order?


-----Input-----

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^4$) — the length of the array.

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

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.


-----Output-----

For each test case of input data, output "YES" (without quotes), if the array may be not sorted in non-decreasing order, output "NO" (without quotes) otherwise. You can output each letter in any case (uppercase or lowercase).


-----Examples-----

Input
3
3
2 2 1
4
3 1 2 1
5
1 2 2 4 4
Output
YES
YES
NO


-----Note-----

In the first test case, it's possible to select $len = 1$, then after operation, the array will not be sorted in non-decreasing order and will be equal to $[2, 1, 2]$.

In the second test case, it's possible to select $len = 3$, then after operation, the array will not be sorted in non-decreasing order and will be equal to $[1, 2, 3, 1]$.

In the third test case, the array will be sorted in non-decreasing order for every possible $len$.

Difficulty: EASY
Tags: Sorting

Complete search
Skill types: Sorting

Complete search

Starter code:

Solutions:
for some_random_name in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	if a == b:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	nn = list(map(int, input().split()))
	if nn == sorted(nn):
		print('NO')
	else:
		print('YES')


n = int(input())
for i in range(n):
	l = int(input())
	A = [int(c) for c in input().split(' ')]
	sted = False
	for j in range(l - 1):
		if A[j] > A[j + 1]:
			sted = True
			break
	if sted:
		print('YES')
	else:
		print('NO')


def solver():
	n = int(input())
	for _ in range(n):
		l = int(input())
		arr = list(map(int, input().split()))
		arr1 = sorted(arr)
		if arr == arr1:
			print('NO')
		else:
			print('YES')
solver()


t = int(input())
for _ in range(t):
	n = int(input())
	k = list(map(int, input().split()))
	l = []
	for i in k:
		l.append(i)
	k.sort()
	if l == k:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	k = []
	k.extend(l)
	count = 0
	l.sort()
	for i in range(a):
		if l[i] == k[i]:
			count += 1
	if count == a:
		print('NO')
	else:
		print('YES')


t = int(input())
ans = []
for x in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	possible = 'NO'
	for y in range(n - 1):
		if a[y] <= a[y + 1]:
			continue
		else:
			possible = 'YES'
			break
	ans.append(possible)
for a in ans:
	print(a)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a == sorted(a):
		print('NO')
	else:
		print('YES')


T = int(input())
ans = []
for test in range(T):
	l = int(input())
	d1 = input()
	D = d1.split()
	D = list(map(int, D))
	original = D.copy()
	D.sort()
	case = D == original
	ans.append(case)
for t in ans:
	if t == False:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	flag = True
	if a == sorted(a):
		print('NO')
	else:
		print('YES')


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


t = int(input())
for i in range(t):
	n = int(input())
	lt = list(map(int, input().split()))
	k = lt.copy()
	if sorted(k) == lt:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	array_n = [int(x) for x in input().split()]
	print('YES' if array_n != sorted(array_n) else 'NO')


for i in range(int(input())):
	n = int(input())
	X = [int(j) for j in input().split()]
	k = 0
	for j in range(n - 1):
		if X[j] > X[j + 1]:
			k = 1
	if k == 1:
		print('YES')
	else:
		print('NO')


for _ in range(0, int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	if b == sorted(b):
		print('NO')
	else:
		print('YES')


num_cases = int(input())
for i in range(num_cases):
	total_nums = int(input())
	num_list = list(map(int, input().split()))
	ordered = True
	for i in range(1, total_nums):
		if num_list[i] < num_list[i - 1]:
			ordered = False
			break
	if ordered:
		print('NO')
	else:
		print('YES')


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

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

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

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

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

def solve(a):
	for i in range(1, len(a)):
		if a[i - 1] > a[i]:
			return 'YES'
	return 'NO'
for _ in range(inp()):
	_ = inp()
	print(solve(read_int_list()))


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	if sorted(a) == a:
		print('NO')
	else:
		print('YES')


import sys

def solve():
	sys.stdin.readline()
	arr = sys.stdin.readline().rstrip('\n').split(' ')
	arr = [int(_) for _ in arr]
	if sorted(arr) == arr:
		print('NO')
	else:
		print('YES')
	return
T = sys.stdin.readline().rstrip('\n')
T = int(T)
for i in range(T):
	solve()


for i in range(int(input())):
	ab = int(input())
	abc = list(map(int, input().split()))
	if sorted(abc) == abc:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	flag = False
	arr = list(map(int, input().split()))
	for i in range(1, n):
		if arr[i - 1] > arr[i]:
			flag = True
	if flag == True:
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	a = int(input())
	arr = list(map(int, input().split()))
	if arr == sorted(arr):
		print('NO')
	else:
		print('YES')


import math
t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	flag = False
	for i in range(n - 1):
		if arr[i] > arr[i + 1]:
			flag = True
	if flag:
		print('YES')
	else:
		print('NO')


def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	max_ = 0
	f = 0
	for num in nums:
		if max_ > num:
			f = 1
			break
		max_ = max(max_, num)
	if f:
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	solve()


t = int(input())
for i in range(t):
	n = int(input())
	m = input().split()
	m = [int(i) for i in m]
	k = [int(i) for i in m]
	m.sort()
	if m == k:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	k = int(input())
	list1 = list(map(int, input().split()))
	list2 = sorted(list1)
	if list1 == list2:
		print('NO')
	else:
		print('YES')


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if a == sorted(a):
		print('NO')
	else:
		b = sorted(a)
		for i in range(n):
			if sorted(a[:i]) + sorted(a[n - i - 1:]) != b:
				print('YES')
				break
		else:
			print('NO')


x = int(input(''))
for i in range(x):
	y = input('')
	z = list(input('').split(' '))
	zfi = z[0]
	u = 0
	for i in z:
		if int(zfi) > int(i):
			print('YES')
			u = 1
			break
		else:
			zfi = i
	if u == 0:
		print('NO')


for i in range(int(input())):
	a = int(input())
	x = list(map(int, input().split()))
	y = x.copy()
	y.sort()
	if x == y:
		print('NO')
	else:
		print('YES')


def fun(test_case):
	mx_arr1 = test_case[0]
	for i in range(1, len(test_case)):
		if mx_arr1 > test_case[i]:
			print('YES')
			break
		else:
			mx_arr1 = test_case[i]
	else:
		print('NO')
n_test_cases = int(input())
test_cases = []
for i in range(n_test_cases):
	n = int(input())
	test_cases.append(list(map(int, input().split(' '))))
for i in range(n_test_cases):
	fun(test_cases[i])


from sys import maxsize

def ga():
	return list(map(int, input().split()))
for _ in range(int(input())):
	n = int(input())
	arr = ga()
	cantSort = False
	for i in range(1, n):
		if arr[i] < arr[i - 1]:
			cantSort = True
			break
	if cantSort:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if sorted(arr) == arr:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	l = int(input())
	arr = list(map(int, input().split()))
	arr1 = sorted(arr)
	if arr == arr1:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	b.sort()
	if a != b:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = l[:]
	c.sort()
	if c == l:
		print('NO')
	else:
		print('YES')


def solve():
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = sorted(a)
	for i in range(n):
		if a[i] == b[i]:
			continue
		else:
			print('YES')
			return
	print('NO')
	return
t = int(input())
while t > 0:
	solve()
	t -= 1


cases = int(input())
for case in range(cases):
	n = int(input())
	items = list(map(int, input().split()))
	if items == sorted(items):
		print('NO')
	else:
		print('YES')


T = int(input())
for _ in range(T):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	i = 0
	m = 1000000
	p = a[0]
	c = 0
	for j in a:
		if p > j:
			c += 1
		else:
			p = j
	if c:
		print('YES')
	else:
		print('NO')


testCases = int(input())
for case in range(testCases):
	numCount = int(input())
	nums = [int(x) for x in input().split(' ')]
	last = 0
	for x in nums:
		if x < last:
			print('YES')
			break
		last = x
	if last == x:
		print('NO')


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


def check(arr):
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1] and len(arr) > 1:
			return 'YES'
	return 'NO'
res = []
total = input()
for i in range(int(total)):
	origin = []
	l = input()
	origin = input()
	origin = origin.split()
	for j in range(int(l)):
		origin[j] = int(origin[j])
	res.append(check(origin))
for x in res:
	print(x)


n = int(input())
for i in range(n):
	l = int(input())
	f = 1
	s = input()
	lis = s.split(' ')
	lis1 = []
	for j in range(l):
		lis[j] = int(lis[j])
		lis1.append(lis[j])
	lis1.sort()
	for k in range(l):
		if lis1[k] != lis[k]:
			f = 0
			break
	if f:
		print('NO')
	else:
		print('YES')


T = int(input())
for i in range(T):
	n = int(input())
	daftar = list(map(int, input().split()))
	if daftar != sorted(daftar):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split()))
	srtlst = sorted(arr)
	if srtlst == arr:
		print('NO')
	else:
		print('YES')


def run(n, data):
	max_arr = [data[0]]
	min_arr = [data[-1]]
	for (x, y) in zip(data[1:], data[::-1][1:]):
		if x > max_arr[-1]:
			max_arr.append(x)
		else:
			max_arr.append(max_arr[-1])
		if y < min_arr[-1]:
			min_arr.append(y)
		else:
			min_arr.append(min_arr[-1])
	min_arr = min_arr[::-1]
	for i in range(n - 1):
		if max_arr[i] > min_arr[i + 1]:
			return 'YES'
	return 'NO'
test_nums = int(input())
ans = []
for _ in range(test_nums):
	n = int(input())
	data = input().split(' ')
	data = [int(x) for x in data]
	ans.append(run(n, data))
for x in ans:
	print(x)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if not all((arr[i] <= arr[i + 1] for i in range(n - 1))):
		print('YES')
	else:
		print('NO')


t = int(input())
tc = 0
while tc < t:
	tc += 1
	n = int(input())
	a = [int(_) for _ in input().split()]
	i = 0
	sorted = True
	while i < n - 1:
		if a[i] > a[i + 1]:
			sorted = False
		i += 1
	if not sorted:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	can = False
	if sorted(nums) == nums:
		can = True
	if can:
		print('NO')
	else:
		print('YES')


ans = []
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if arr == sorted(arr):
		ans.append('NO')
	else:
		ans.append('YES')
for x in ans:
	print(x)


for _ in [*open(0)][2::2]:
	arr = list(map(int, _.split()))
	print('YNEOS'[arr == sorted(arr)::2])


n = int(input())
for i in range(n):
	p = int(input())
	l = [int(i) for i in input().split()]
	t = sorted(l)
	if l == t:
		print('NO')
	else:
		print('YES')


for s in [*open(0)][2::2]:
	print('YNEOS'[sorted((a := s.split()), key=int) == a::2])


for _ in range(int(input())):
	n = int(input())
	a = [int(_) for _ in input().split()]
	print('YNEOS'[sorted(a) == a::2])


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = sorted(l)
	if l == k:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	input()
	s = list(map(int, str.split(input())))
	print('NO' if s == list(sorted(s)) else 'YES')


def solve():
	n = int(input())
	l = list(map(int, input().split(' ')))
	s = sorted(l)
	if l == s:
		print('NO')
	else:
		print('YES')
for _ in range(int(input())):
	solve()


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	f = 0
	b = a[:]
	b.sort()
	if b == a:
		f = 1
	if f:
		print('NO')
	else:
		print('YES')


t = int(input())
for zz in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	if l1 == l:
		print('NO')
	else:
		print('YES')


import math
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	y = x[:]
	x.sort()
	if x == y:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	f = False
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			f = True
	if f:
		print('YES')
	else:
		print('NO')


for fortnite_top in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	z = 0
	for i in range(1, n):
		if l[i] >= l[i - 1]:
			pass
		else:
			z = 1
	if z == 1:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	ad = int(input())
	l = list(map(int, input().split(' ')))
	a = True
	for j in range(1, ad):
		if l[j] < l[j - 1]:
			a = not a
			break
	if a:
		print('NO')
	else:
		print('YES')


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_list_string():
	return list(map(str, sys.stdin.readline().strip().split()))

def get_string():
	return sys.stdin.readline().strip()

def get_int():
	return int(sys.stdin.readline().strip())

def get_print_int(x):
	sys.stdout.write(str(x) + '\n')

def get_print(x):
	sys.stdout.write(x + '\n')

def get_print_int_same(x):
	sys.stdout.write(str(x) + ' ')

def get_print_same(x):
	sys.stdout.write(x + ' ')

def solve():
	for _ in range(get_int()):
		n = get_int()
		arr = get_list()
		sarr = sorted(arr)
		ans = 'NO'
		for i in range(n):
			if arr[i] != sarr[i]:
				ans = 'YES'
				break
		get_print(ans)
solve()


import sys
input = sys.stdin.readline

def ii():
	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 f(ls):
	return 'NO' if sorted(ls) == ls else 'YES'
for _ in range(ii()):
	_ = ii()
	print(f(inlt()))


a = int(input())
for i in range(a):
	input()
	b = list(map(int, input().split()))
	if sorted(b) == b:
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	a1 = sorted(a)
	if a == a1:
		print('NO')
	else:
		print('YES')


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


def processing(data, n):
	data_copy = data.copy()
	data_copy.sort()
	for i in range(n):
		if data_copy[i] != data[i]:
			return 'YES'
	return 'NO'
t = int(input())
while t > 0:
	n = int(input())
	list_input = [int(i) for i in input().split()]
	print(processing(list_input, n))
	t -= 1


def read_single_num():
	return int(input())

def read_nums():
	return list(map(int, input().split()))
t = read_single_num()
for i in range(t):
	n = read_single_num()
	arr = read_nums()
	if arr == list(sorted(arr)):
		print('NO')
	else:
		print('YES')


for __ in range(int(input())):
	n = int(input())
	ar = list(map(int, input().split()))
	ans = 'NO'
	for i in range(1, n):
		if ar[i] < ar[i - 1]:
			ans = 'YES'
	print(ans)


inp = __import__('sys').stdin.readline
T = int(inp())
for t in range(T):
	N = int(inp())
	ar = list(map(int, inp().split()))
	print('YES' if ar != sorted(ar) else 'NO')


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	if s == sorted(s):
		print('NO')
	else:
		print('YES')