JJ has an array A. He can perform the following operation on A:
Divide A into two subsequences P and Q such that each A_{i} belongs to either P or Q.
Set A := P\ \texttt{concat}\ Q  

Here \texttt{concat} denotes the concatenation operation. For e.g. [2, 1, 5] \texttt{ concat } [4, 3] = [2, 1, 5, 4, 3].

Is it possible to make A sorted in non-decreasing order after applying the above operation at most once?

Note: An array X is a subsequence of an array Y if X can be obtained by deletion of several (possibly, zero or all) elements from Y.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — the size of the array A.
- The second line of each test case contains N space-separated integers A_{1}, A_{2}, \ldots, A_{N} denoting the array A.

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

For each test case, output YES if it is possible to make the array A sorted after applying the given operation at most once. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

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

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

----- Sample Input 1 ------ 
3
6
4 5 6 1 2 3
5
1 3 5 2 4
5
5 10 7 11 9

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

----- explanation 1 ------ 
Test case $1$: We can select $P = [1, 2, 3]$ and $Q = [4, 5, 6]$. Therefore $A$ will become $[1, 2, 3, 4, 5, 6]$ which is sorted.

Test case $2$: It can be proven that it is not possible to sort $A$ by using the given operation at most once.

Test case $3$: We can select $P = [5, 7, 9]$ and $Q = [10, 11]$. Therefore $A$ will become $[5, 7, 9, 10, 11]$ which is sorted.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Implementation

Greedy algorithms


Solutions:
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a1 = sorted(a)
	x = y = []
	start = 0
	for i in range(n):
		if a1[start] != a[i]:
			x.append(a[i])
		else:
			start += 1
	if x == []:
		print('YES')
	elif x == sorted(x):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	nli = list(map(int, input().split()))
	srtli = list()
	srtli += nli
	srtli.sort()
	pli = list()
	qli = list()
	ind_srt = 0
	for a in nli:
		if srtli[ind_srt] == a:
			pli.append(a)
			ind_srt += 1
		else:
			qli.append(a)
	pq = pli + qli
	if srtli == pq:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(z) for z in input().split()]
	b = sorted(a)
	c = [a.index(b[0]), 0]
	d = [0] * n
	for i in range(2):
		c[0] = 0
		while c[0] < n:
			if not d[c[0]] and a[c[0]] == b[c[1]]:
				d[c[0]] = 1
				c[0] += 1
				c[1] += 1
			else:
				c[0] += 1
	print('YES' if c[0] == c[1] else 'NO')


for _ in range(int(input())):
	num = int(input())
	array_1 = list(map(int, input().split()))[:num]
	array_2 = sorted(array_1)
	array_3 = [array_1.index(array_2[0]), 0]
	null_array_1 = [0] * num
	for i in range(2):
		array_3[0] = 0
		while array_3[0] < num:
			if not null_array_1[array_3[0]] and array_1[array_3[0]] == array_2[array_3[1]]:
				null_array_1[array_3[0]] = 1
				array_3[0] += 1
				array_3[1] += 1
			else:
				array_3[0] += 1
	if array_3[0] == array_3[1]:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	j = 0
	s = []
	f = sorted(l)
	for i in range(n):
		if l[i] == f[j]:
			j = j + 1
		else:
			s.append(l[i])
	ss = sorted(s)
	if s == ss:
		print('YES')
	else:
		print('NO')


def find_flop_ind(arr):
	if len(arr) <= 1:
		return -1
	for ind in range(len(arr) - 1):
		if arr[ind] > arr[ind + 1]:
			return ind + 1
	return -1

def solve(arr):
	ind = find_flop_ind(arr)
	if ind == -1:
		return True
	q_ind = 0
	while q_ind < ind:
		if arr[q_ind] > arr[ind]:
			break
		q_ind += 1
	q0 = arr[q_ind]
	P = [(i, loc) for (loc, i) in enumerate(arr) if i < q0]
	Q = [(i, loc) for (loc, i) in enumerate(arr) if i > q0]
	R = [(i, loc) for (loc, i) in enumerate(arr) if i == q0]
	c1 = find_flop_ind(P) == -1 and find_flop_ind(Q) == -1
	if len(Q) == 0 or len(P) == 0:
		return c1
	p_end = 0
	while p_end < len(R):
		i = R[p_end]
		if i[1] > P[-1][1]:
			break
		p_end += 1
	return c1 and (R[p_end - 1][1] < Q[0][1] if p_end != 0 else True)
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]
	print('YES' if solve(arr) else 'NO')


T = int(input())
for i in range(T):
	N = int(input())
	A = input()
	x = list(map(int, A.split(' ')))
	q = []
	p = []
	s = sorted(x)
	j = 0
	for i in s:
		while j < len(x):
			if x[j] == i:
				p.append(i)
				j = j + 1
				break
			q.append(x[j])
			j = j + 1
	res = 'YES' if p + q == s else 'NO'
	print(res)


T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	sortA = sorted(A)
	possible = True
	(s1, s2) = ([], [])
	(i, j) = (0, 0)
	while i < n:
		if A[i] == sortA[j]:
			s1.append(A[i])
			i += 1
			j += 1
		else:
			s2.append(A[i])
			i += 1
	for i in range(len(s2) - 1):
		if s2[i] > s2[i + 1]:
			possible = False
			break
	if possible:
		print('YES')
	else:
		print('NO')


from functools import cmp_to_key
import math
from pydoc import doc

def run(debug=True):
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		sortedArr = sorted(arr)
		rem = []
		curr = 0
		for i in range(n):
			if arr[i] == sortedArr[curr]:
				curr += 1
				continue
			else:
				rem.append(arr[i])
		remSorted = sorted(rem)
		poss = True
		for i in range(len(rem)):
			if rem[i] != remSorted[i]:
				poss = False
				break
		print('YES' if poss else 'NO')
while True:
	try:
		run(False)
	except:
		break


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	arr_2 = sorted(arr)
	arr_3 = [arr.index(arr_2[0]), 0]
	null_arr = [0] * n
	for i in range(2):
		arr_3[0] = 0
		while arr_3[0] < n:
			if not null_arr[arr_3[0]] and arr[arr_3[0]] == arr_2[arr_3[1]]:
				null_arr[arr_3[0]] = 1
				arr_3[0] += 1
				arr_3[1] += 1
			else:
				arr_3[0] += 1
	if arr_3[0] == arr_3[1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	x = l.copy()
	l.sort()
	if x == l:
		print('YES')
		continue
	cur = 0
	m = []
	for i in x:
		if i == l[cur]:
			cur += 1
		else:
			m.append(i)
	if l[cur] <= m[0]:
		f = m.copy()
		m.sort()
		if m == f:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


try:
	for _ in range(int(input())):
		n = int(input())
		arr = list(map(int, input().split()))
		new_arr = sorted(arr)
		List_new = []
		i = 0
		j = 0
		while i < n:
			if arr[i] == new_arr[j]:
				arr[i] = -1
				i += 1
				List_new.append(new_arr[j])
				j += 1
			else:
				i += 1
		for val in arr:
			if val != -1:
				List_new.append(val)
		if List_new == new_arr:
			print('YES')
		else:
			print('NO')
except:
	pass


n = int(input())
for i in range(n):
	m = int(input())
	original = list(map(int, input().split(' ')))
	l = original.copy()
	original.sort()
	index = 0
	l1 = []
	l2 = []
	for item in l:
		if item == original[index]:
			l1.append(item)
			index += 1
		else:
			l2.append(item)
	if l1 + l2 == original:
		print('YES')
	else:
		print('NO')


ans = []
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	sA = sorted(A)
	(p, old) = (0, float('-inf'))
	for a in A:
		if a == sA[p]:
			p += 1
		else:
			if old > a:
				break
			old = a
	else:
		ans.append('YES')
		continue
	ans.append('NO')
print(*ans, sep='\n')


ans = []
for _ in range(int(input())):
	N = int(input())
	A = [int(x) for x in input().split()]
	sA = sorted(A)
	(p, A2, an) = (0, [], 'YES')
	for a in A:
		if a == sA[p]:
			p += 1
		else:
			A2.append(a)
	for i in range(1, len(A2)):
		if A2[i - 1] > A2[i]:
			break
	else:
		ans.append('YES')
		continue
	ans.append('NO')
print(*ans, sep='\n')


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	s = [i for i in l]
	s.sort()
	j = 0
	ans = []
	for i in range(n):
		if s[j] == l[i]:
			j += 1
		else:
			ans.append(l[i])
	flag = 1
	for i in range(len(ans) - 1):
		if ans[i] > ans[i + 1]:
			flag = 0
	if flag:
		print('YES')
	else:
		print('NO')


def isSorted(arr):
	for i in range(1, len(arr)):
		if arr[i] < arr[i - 1]:
			return False
	return True

def solve(arr, n):
	b = sorted(arr)
	curr = 0
	rem = []
	for i in range(n):
		if arr[i] == b[curr]:
			curr += 1
		else:
			rem.append(arr[i])
	if isSorted(rem):
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(solve(arr, n))


for _ in range(int(input())):
	n = int(input())
	cpraid1 = [int(z) for z in input().split()]
	cpraid2 = sorted(cpraid1)
	cpraid3 = [cpraid1.index(cpraid2[0]), 0]
	cpraid4 = [0] * n
	for i in range(2):
		cpraid3[0] = 0
		while cpraid3[0] < n:
			if not cpraid4[cpraid3[0]] and cpraid1[cpraid3[0]] == cpraid2[cpraid3[1]]:
				cpraid4[cpraid3[0]] = 1
				cpraid3[0] += 1
				cpraid3[1] += 1
			else:
				cpraid3[0] += 1
	print('YES' if cpraid3[0] == cpraid3[1] else 'NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = arr.copy()
	k.sort()
	i = 0
	j = 0
	first = []
	second = []
	while i < n:
		if arr[i] == k[j]:
			first.append(k[j])
			j += 1
		else:
			second.append(arr[i])
		i = i + 1
	if first + second == k:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = sorted(l)
	l2 = []
	l3 = []
	j = 0
	for k in range(n):
		if l[k] == l1[j]:
			l2.append(l[k])
			j += 1
		else:
			l3.append(l[k])
	if l2 == sorted(l2) and l3 == sorted(l3):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	n = int(input())
	arr = [int(i) for i in input().split(' ')]
	sorted_arr = sorted(arr)
	l1 = []
	l2 = []
	j = 0
	for i in range(n):
		if arr[i] == sorted_arr[j]:
			l1.append(arr[i])
			j += 1
		else:
			l2.append(arr[i])
	if l1 == sorted(l1) and l2 == sorted(l2):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr = [int(i) for i in input().split()][:n]
	sorted_array = sorted(arr)
	half = []
	second = []
	j = 0
	for i in range(n):
		if arr[i] == sorted_array[j]:
			half.append(arr[i])
			j += 1
		else:
			second.append(arr[i])
	if second == sorted(second):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	lis = list(map(int, input().split()))
	new = sorted(lis)
	j = 0
	temp = []
	for i in range(n):
		if lis[i] == new[j]:
			j += 1
		else:
			temp.append(lis[i])
	if sorted(temp) == temp:
		print('YES')
	else:
		print('NO')
	t -= 1


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	d = sorted(a)
	b = []
	c = []
	i = 0
	j = 0
	while i < n:
		if a[i] == d[j]:
			b.append(a[i])
			i += 1
			j += 1
		else:
			c.append(a[i])
			i += 1
	e = sorted(c)
	if c == e:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ls = sorted(l)
	j = 0
	b = []
	for i in l:
		if i == ls[j]:
			j += 1
		else:
			b.append(i)
	if b == sorted(b):
		print('YES')
	else:
		print('NO')


T = int(input())
for tc in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a_sorted = sorted(a)
	b = []
	j = 0
	for i in a:
		if i == a_sorted[j]:
			j += 1
		else:
			b.append(i)
	if b == sorted(b):
		print('YES')
	else:
		print('NO')


n = float(input())
for i in range(int(n)):
	a = int(input())
	b = input()
	b = b.split(' ')
	c = []
	for i in range(a):
		c.append(float(b[i]))
	k = c.copy()
	c.sort()
	g = k.index(c[0])
	k.remove(c[0])
	d = [c[0]]
	e = []
	f = []
	for i in range(g):
		f.append(k[i])
	for i in range(g, a - 1):
		if k[i] == c[len(d)]:
			d.append(k[i])
		else:
			e.append(k[i])
	if d == sorted(d) and e == sorted(e) and (f == sorted(f)):
		if len(f) == 0:
			print('YES')
		elif len(e) == 0:
			print('YES')
		elif min(e) >= max(f):
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


t = int(input())
for z in range(t):
	m = 0
	l = []
	r = []
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	k = 0
	for i in range(0, len(a)):
		if a[i] == b[k]:
			l.append(a[i])
			k += 1
		else:
			r.append(a[i])
	e = r.copy()
	e.sort()
	for i in range(0, len(e)):
		if e[i] != r[i]:
			m = 1
			break
	if m == 1:
		print('NO')
	else:
		print('YES')


import heapq
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr1 = arr.copy()
	(l, r) = ([], [])
	ans = 'YES'
	heapq.heapify(arr1)
	temp = heapq.heappop(arr1)
	i = 0
	while i < len(arr):
		if arr[i] == temp:
			l.append(arr[i])
			if arr1:
				temp = heapq.heappop(arr1)
			arr[i] = False
		i += 1
	for i in range(len(arr)):
		if arr[i] != False:
			if len(r) == 0:
				r.append(arr[i])
			elif arr[i] >= r[-1]:
				r.append(arr[i])
			else:
				break
	if len(l) + len(r) == len(arr):
		print('YES')
	else:
		print('NO')


t = int(input())
for __ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = a.copy()
	a.sort()
	h = []
	i = 0
	j = 0
	while i < n and j < n:
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			h.append(b[j])
			j += 1
	l = h.copy()
	l.sort()
	if l == h:
		print('YES')
	else:
		print('NO')


def isSorted(rest):
	n = len(rest)
	for i in range(0, n - 1):
		if rest[i] > rest[i + 1]:
			return False
	return True
tc = int(input())
for _ in range(1, 1 + tc):
	n = int(input())
	arr = list(map(int, input().split()))
	if n <= 2:
		print('YES')
		continue
	nums = sorted(arr)
	probe = -1
	shift = 0
	rest = []
	(i, j) = (0, 0)
	while i < n and j < n:
		while j < n and nums[i] != arr[j]:
			rest.append(arr[j])
			j += 1
		i += 1
		j += 1
	if len(rest) == 0 or isSorted(rest):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))
	arr2 = sorted(arr)
	(j, i) = (0, 0)
	(p, q) = ([], [])
	while i < len(arr):
		if arr[i] == arr2[j]:
			p.append(arr[i])
			j += 1
		else:
			q.append(arr[i])
		i += 1
	q2 = sorted(q)
	if q2 == q:
		print('YES')
	else:
		print('NO')
	t -= 1


import copy
t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	p = l.copy()
	p.sort()
	j = 0
	lst = []
	for i in range(n):
		if l[i] == p[j]:
			j += 1
		else:
			lst.append(l[i])
	if len(lst) == 0:
		print('YES')
		continue
	prev = lst[0]
	ans = 'YES'
	for i in lst:
		if i < prev:
			ans = 'NO'
			break
		prev = i
	print(ans)


for _ in range(int(input())):
	n = int(input())
	elliot = list(map(int, input().split()))[:n]
	angela = sorted(elliot)
	tyrell = [elliot.index(angela[0]), 0]
	null_arr = [0] * n
	k = 0
	for i in range(1000):
		k += 1
	for i in range(1000):
		k += 1
	for i in range(2):
		tyrell[0] = 0
		while tyrell[0] < n:
			if not null_arr[tyrell[0]] and elliot[tyrell[0]] == angela[tyrell[1]]:
				null_arr[tyrell[0]] = 1
				tyrell[0] += 1
				tyrell[1] += 1
			else:
				tyrell[0] += 1
	if tyrell[0] == tyrell[1]:
		print('YES')
	else:
		print('NO')


for itr in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split()))[:num]
	arr2 = sorted(arr)
	arr3 = [arr.index(arr2[0]), 0]
	arr4 = [0] * num
	for itr in range(2):
		arr3[0] = 0
		while arr3[0] < num:
			if not arr4[arr3[0]] and arr[arr3[0]] == arr2[arr3[1]]:
				arr4[arr3[0]] = 1
				arr3[0] += 1
				arr3[1] += 1
			else:
				arr3[0] += 1
	if arr3[0] == arr3[1]:
		print('YES')
	else:
		print('NO')


n = int(input())
for t in range(n):
	N = int(input())
	ls = [int(x) for x in input().split()]
	ls_sort = sorted(ls)
	V1 = []
	V2 = []
	i = j = 0
	while j < N:
		if ls_sort[i] == ls[j]:
			V1.append(ls[j])
			i += 1
		else:
			V2.append(ls[j])
		j += 1
	if all((V1[i] <= V1[i + 1] for i in range(len(V1) - 1))) and all((V2[j] <= V2[j + 1] for j in range(len(V2) - 1))):
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	no = int(input())
	array = list(map(int, input().split()))[:no]
	array2 = sorted(array)
	array3 = [array.index(array2[0]), 0]
	null_arr = [0] * no
	for z in range(2):
		array3[0] = 0
		while array3[0] < no:
			if not null_arr[array3[0]] and array[array3[0]] == array2[array3[1]]:
				null_arr[array3[0]] = 1
				array3[0] += 1
				array3[1] += 1
			else:
				array3[0] += 1
	if array3[0] == array3[1]:
		print('YES')
	else:
		print('NO')


T = int(input())
while T > 0:
	n = int(input())
	a = [int(i) for i in input().split(' ')]
	sr = lr = 0
	ans = 'YES'
	for i in range(1, len(a)):
		if sr == 0:
			if a[i] < a[i - 1]:
				lr = a[i - 1]
				sr = a[i]
				j = i - 2
				while True:
					if j == -1 or a[j] <= a[i]:
						ll = a[j + 1]
						break
					else:
						j -= 1
			else:
				continue
		elif a[i] >= lr:
			lr = a[i]
		elif a[i] > ll:
			ans = 'NO'
			break
		elif a[i] >= sr:
			sr = a[i]
		else:
			ans = 'NO'
			break
	print(ans)
	T -= 1


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(num) for num in input().split(' ', n - 1)]
	b = a[:]
	b.sort()
	lst = []
	i = 0
	j = 0
	while i < n and j < n:
		if a[i] == b[j]:
			i += 1
			j += 1
		else:
			lst.append(a[i])
			i += 1
	lst2 = lst[:]
	lst2.sort()
	if lst == lst2:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	arr1 = [int(z) for z in input().split()]
	sorted_arr = sorted(arr1)
	arr3 = [arr1.index(sorted_arr[0]), 0]
	arr4 = [0] * n
	for i in range(0, 2):
		arr3[0] = 0
		while arr3[0] < n:
			if not arr4[arr3[0]] and arr1[arr3[0]] == sorted_arr[arr3[1]]:
				arr4[arr3[0]] = 1
				arr3[0] += 1
				arr3[1] += 1
			else:
				arr3[0] += 1
	if arr3[0] == arr3[1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	temp1 = [int(z) for z in input().split()]
	temp4 = [0] * n
	temp2 = sorted(temp1)
	temp3 = [temp1.index(temp2[0]), 0]
	for i in range(2):
		temp3[0] = 0
		while temp3[0] < n:
			if not temp4[temp3[0]] and temp1[temp3[0]] == temp2[temp3[1]]:
				temp4[temp3[0]] = 1
				temp3[0] += 1
				temp3[1] += 1
			else:
				temp3[0] += 1
	print('YES' if temp3[0] == temp3[1] else 'NO')


for _ in range(int(input())):
	n = int(input())
	li = [int(x) for x in input().split()]
	j = 0
	li1 = []
	li2 = []
	b = sorted(li)
	for i in range(n):
		if b[j] != li[i]:
			li2.append(li[i])
		else:
			j += 1
			li1.append(li[i])
	li1.extend(li2)
	if li1 != b:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	size = int(input())
	a = list(map(int, input().split()))
	tmp = [0] * size
	b = sorted(a)
	c = [a.index(b[0]), 0]
	for j in range(2):
		c[0] = 0
		while c[0] < size:
			if not tmp[c[0]] and a[c[0]] == b[c[1]]:
				c[1] += 1
				tmp[c[0]] = 1
				c[0] += 1
			else:
				c[0] += 1
	if c[0] == c[1]:
		print('YES')
	else:
		print('NO')


t = int(input(''))
while t > 0:
	n = int(input())
	arr = list(map(int, input().split()))[:n]
	arrS = sorted(arr)
	arrI = [arr.index(arrS[0]), 0]
	arr0 = [0] * n
	for i in range(2):
		arrI[0] = 0
		while arrI[0] < n:
			if not arr0[arrI[0]] and arr[arrI[0]] <= arrS[arrI[1]]:
				arr0[arrI[0]] = 1
				arrI[0] += 1
				arrI[1] += 1
			else:
				arrI[0] += 1
	if arrI[0] == arrI[1]:
		print('YES')
	else:
		print('NO')
	t -= 1


for test in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	t = l.copy()
	t = sorted(t)
	check = 0
	for i in range(n):
		if l[i] == t[check]:
			check += 1
	for j in range(n):
		if check < n:
			if l[j] == t[check]:
				check += 1
		else:
			break
	if check == n:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))[:n]
	B = sorted(A)
	C = [A.index(B[0]), 0]
	null_A = [0] * n
	for i in range(2):
		C[0] = 0
		while C[0] < n:
			if not null_A[C[0]] and A[C[0]] == B[C[1]]:
				null_A[C[0]] = 1
				C[0] += 1
				C[1] += 1
			else:
				C[0] += 1
	if C[0] == C[1]:
		print('YES')
	else:
		print('NO')


def sol(arr, n):
	arrs = sorted(arr)
	maxx = 0
	for i in range(n):
		if arr[i] == arrs[maxx]:
			maxx += 1
	for j in range(n):
		if maxx == n:
			break
		elif arr[j] == arrs[maxx]:
			maxx += 1
	if maxx >= n:
		print('YES')
	else:
		print('NO')
T = int(input())
while T > 0:
	N = int(input())
	arr = list(map(int, input().split()))
	sol(arr, N)
	T -= 1


for testcases in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = sorted(a)
	c = []
	j = k = flag = 0
	for i in range(n):
		if a[i] == b[j]:
			j += 1
		else:
			c.insert(k, a[i])
			k += 1
	if c != sorted(c):
		flag = 1
	if flag:
		print('NO')
	else:
		print('YES')


for i in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	temp = [int(i) for i in range(n)]
	l2 = sorted(l)
	l3 = []
	l3.append(l.index(l2[0]))
	l3.append(0)
	temp.sort(reverse=True)
	res = [0] * n
	for i in range(2):
		l3[0] = 0
		while l3[0] < n:
			if not res[l3[0]] and l[l3[0]] == l2[l3[1]]:
				res[l3[0]] = 1
				l3[0] += 1
				l3[1] += 1
			else:
				l3[0] += 1
	if l3[0] == l3[1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	nkri = int(input())
	arrkri = list(map(int, input().split()))[:nkri]
	arrkri_2 = sorted(arrkri)
	arrkri_3 = [arrkri.index(arrkri_2[0]), 0]
	null_arrkri = [0] * nkri
	for ikri in range(2):
		arrkri_3[0] = 0
		while arrkri_3[0] < nkri:
			if not null_arrkri[arrkri_3[0]] and arrkri[arrkri_3[0]] == arrkri_2[arrkri_3[1]]:
				null_arrkri[arrkri_3[0]] += 1
				arrkri_3[0] += 1
				arrkri_3[1] += 1
			else:
				arrkri_3[0] += 1
	if arrkri_3[0] == arrkri_3[1]:
		print('YES')
	else:
		print('NO')


from sys import stdin, stdout, stderr, setrecursionlimit
from math import pi, sqrt, gcd, ceil, floor, log2, log10, factorial
from math import cos, acos, tan, atan, atan2, sin, asin, radians, degrees, hypot
from bisect import insort, insort_left, insort_right, bisect_left, bisect_right, bisect
from functools import reduce
from itertools import combinations, combinations_with_replacement, permutations
from fractions import Fraction
from random import choice, getrandbits, randint, random, randrange, shuffle
from re import compile, findall, escape, search, match
from statistics import mean, median, mode
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, merge, nlargest, nsmallest
from collections import deque, OrderedDict, defaultdict
from collections import Counter, namedtuple, ChainMap, UserDict, UserList, UserString
import time
import math

def prime_number(start, end):
	l = []
	for num in range(start, end):
		if num > 1:
			for i in range(2, num):
				if num % i == 0:
					break
			else:
				l.append(num)
	return l

def findbin(a):
	return bin(a)

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			print(p)

def primeornot(num):
	if num > 1:
		for i in range(2, num):
			if num % i == 0:
				print(num, 'is not a prime number')
				break
			else:
				print(num, 'is a prime number')
	else:
		print(num, 'is not a prime number')

def numSuba1ayProductLessThanK(nums, k):
	if k <= 1:
		return 0
	prod = 1
	ans = left = 0
	for (right, val) in enumerate(nums):
		prod *= val
		while prod >= k:
			prod /= nums[left]
			left += 1
		ans += right - left + 1
	return ans
mod = 10 ** 9 + 7
lcm = lambda x, y: x * y // gcd(x, y)
add = lambda x, y: (x % mod + y % mod) % mod
sub = lambda x, y: (x % mod - y % mod + mod) % mod
mul = lambda x, y: x % mod * (y % mod) % mod
inverse = lambda x: pow(x, mod - 2, mod)
setBitCount = lambda x: bin(x).count('1')
sumOfDigits = lambda x: sum([int(i) for i in str(x)])
start_time = time.time()
for _ in range(int(input())):
	n = int(input())
	lcm = lambda x, y: x * y // gcd(x, y)
	add = lambda x, y: (x % mod + y % mod) % mod
	sub = lambda x, y: (x % mod - y % mod + mod) % mod
	a1 = list(map(int, input().split()))
	a2 = list(sorted(a1))
	lcm = lambda x, y: x * y // gcd(x, y)
	add = lambda x, y: (x % mod + y % mod) % mod
	sub = lambda x, y: (x % mod - y % mod + mod) % mod
	a3 = [a1.index(a2[0]), 0]
	local = [0] * n
	for i in range(2):
		a3[0] = 0
		while a3[0] < n:
			if not local[a3[0]] and a1[a3[0]] == a2[a3[1]]:
				local[a3[0]] = 1
				a3[0] += 1
				a3[1] += 1
			else:
				a3[0] += 1
	lcm = lambda x, y: x * y // gcd(x, y)
	add = lambda x, y: (x % mod + y % mod) % mod
	sub = lambda x, y: (x % mod - y % mod + mod) % mod
	if a3[0] == a3[1]:
		print('YES')
	else:
		print('NO')
end_time = time.time()