An array A of length N is said to be *pseudo-sorted* if it can be made non-decreasing after performing the following operation at most once.
Choose an i such that 1 ≤ i ≤ N-1 and swap A_{i} and A_{i+1}

Given an array A, determine if it is *pseudo-sorted* or not.

------ 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}, \dots, A_{N} denoting the array A.

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

For each testcase, output YES if the array A is pseudo-sorted, NO otherwise.

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 ≤ 1000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ over all test cases do not exceed $2 \cdot 10^{5}$

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

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

----- explanation 1 ------ 
Test case 1: The array is already sorted in non-decreasing order.

Test case 2: We can choose $i = 2$ and swap $A_{2}$ and $A_{3}$. The resulting array will be $[1, 2, 3, 3]$, which is sorted in non-decreasing order.

Test case 3: It can be proven that the array cannot be sorted in non-decreasing order in at most one operation.

Difficulty: EASY
Tags: Implementation

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a)
	ans = 'YES'
	moves = 0
	for x in range(len(a)):
		if a[x] != b[x]:
			if x == len(a) - 1:
				ans = 'NO'
			else:
				(a[x], a[x + 1]) = (a[x + 1], a[x])
				moves += 1
	if moves > 1:
		ans = 'NO'
	print(ans)


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


def is_sort(l):
	for i in range(0, n):
		for j in range(0, n - i - 1):
			if l[j] > l[j + 1]:
				(l[j], l[j + 1]) = (l[j + 1], l[j])
				return l
for _ in range(int(input())):
	n = int(input())
	arr1 = list(map(int, input().split()))
	arr2 = arr1[:]
	arr2.sort()
	if arr1 == arr2:
		print('YES')
	else:
		x = is_sort(arr1)
		if x == arr2:
			print('YES')
		else:
			print('NO')


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


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


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


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


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


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


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


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


def main(A):
	cnt = 0
	change = True
	while change:
		change = False
		for i in range(1, len(A)):
			if A[i] < A[i - 1]:
				(A[i], A[i - 1]) = (A[i - 1], A[i])
				cnt = cnt + 1
				if cnt > 1:
					print('NO')
					return
				change = True
	print('YES')
for x in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	main(A)


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


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


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


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


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


t = int(input())
for u in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	a = l.copy()
	l.sort()
	if l == a:
		print('YES')
	else:
		for i in range(0, n - 1):
			if a[i] > a[i + 1]:
				(a[i], a[i + 1]) = (a[i + 1], a[i])
				c = c + 1
		if l == a and c == 1:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	B = []
	B.extend(A)
	B.sort()
	c = 0
	for j in range(N - 1):
		if A[j] > A[j + 1]:
			t = A[j]
			A[j] = A[j + 1]
			A[j + 1] = t
			break
	for j in range(N):
		if A[j] == B[j]:
			c += 1
	if c == N:
		print('YES')
	else:
		print('NO')


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


import copy
for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	m = copy.copy(l)
	h = 0
	m.sort()
	if m == l:
		print('YES')
	else:
		for j in range(a - 1):
			y = l[j]
			l[j] = l[j + 1]
			l[j + 1] = y
			if m == l:
				h += 1
			r = l[j]
			l[j] = l[j + 1]
			l[j + 1] = r
		if h > 0:
			print('YES')
		else:
			print('NO')


T = int(input())
for _ in range(T):
	n = int(input())
	l = list(map(int, input().split()))
	s = l[:]
	s.sort()
	down = 0
	for i in range(1, n):
		if l[i] < l[i - 1]:
			(l[i], l[i - 1]) = (l[i - 1], l[i])
			break
	print('YES' if l == s else 'NO')


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


def cook(arr):
	temp = arr
	temp = sorted(temp)
	if temp == arr:
		return 'YES'
	else:
		for i in range(len(arr) - 1):
			(arr[i + 1], arr[i]) = (arr[i], arr[i + 1])
			if temp == arr:
				return 'YES'
			else:
				(arr[i + 1], arr[i]) = (arr[i], arr[i + 1])
	return 'NO'
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().strip().split()))[:n]
	print(cook(arr))


testcases = int(input())
while testcases > 0:
	N = int(input())
	li = list(map(int, input().split()))
	count = 0
	for i in range(N - 1):
		if li[i] > li[i + 1]:
			temp = li[i]
			li[i] = li[i + 1]
			li[i + 1] = temp
			break
	for i in range(N - 1):
		if li[i] > li[i + 1]:
			count += 1
	if count == 0:
		print('YES')
	else:
		print('NO')
	testcases -= 1


s = int(input())
for i in range(s):
	a = int(input())
	b = list(map(int, input().split(' ')))
	s = b[:]
	s.sort()
	for j in range(a - 1):
		if b[j] > b[j + 1]:
			(b[j], b[j + 1]) = (b[j + 1], b[j])
			break
	if b == s:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	x = sorted(l)
	c = []
	if x == l:
		print('YES')
	else:
		for i in range(n):
			p = l[i] - x[i]
			if p != 0:
				c.append(i)
		if len(c) > 2:
			print('NO')
		elif len(c) == 2:
			for i in range(len(c) - 1):
				if abs(c[i] - c[i + 1]) > 1:
					print('NO')
				else:
					print('YES')
		else:
			print('NO')


n = int(input())
for i in range(n):
	r = int(input())
	a = list(map(int, input().split()))
	flag = 0
	b = [i for i in a]
	b.sort()
	for i in range(1, len(a)):
		if a[i] < a[i - 1] and flag == 0:
			flag = 1
			d = a[i]
			a[i] = a[i - 1]
			a[i - 1] = d
	tag = 0
	for i in range(len(a)):
		if a[i] != b[i]:
			tag = -1
	if tag == -1:
		print('NO')
	else:
		print('YES')


def pseudo(a):
	temp = a
	temp = sorted(a)
	if temp == a:
		return 'YES'
	else:
		for i in range(len(a) - 1):
			(a[i + 1], a[i]) = (a[i], a[i + 1])
			if temp == a:
				return 'YES'
			else:
				(a[i + 1], a[i]) = (a[i], a[i + 1])
	return 'NO'
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(pseudo(a))