Larry has been given a permutation of a sequence of natural numbers incrementing from $\mbox{1}$ as an array.  He must determine whether the array can be sorted using the following operation any number of times:  

Choose any $3$ consecutive indices and rotate their elements in such a way that $ABC\:\to\text{}BCA\:\to\text{}CAB\:\to\text{}ABC$. 

For example, if $A=\{1,6,5,2,4,3\}$:

A		rotate 
[1,6,5,2,4,3]	[6,5,2]
[1,5,2,6,4,3]	[5,2,6]
[1,2,6,5,4,3]	[5,4,3]
[1,2,6,3,5,4]	[6,3,5]
[1,2,3,5,6,4]	[5,6,4]
[1,2,3,4,5,6]

YES

On a new line for each test case, print YES if $\mbox{A}$ can be fully sorted.  Otherwise, print NO.  

Function Description  

Complete the larrysArray function in the editor below.  It must return a string, either YES or NO.  

larrysArray has the following parameter(s):  

A: an array of integers  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.   

The next $\boldsymbol{\boldsymbol{t}}$ pairs of lines are as follows:  

The first line contains an integer $n$, the length of $\mbox{A}$.
The next line contains $n$ space-separated integers $A[i]$.

Constraints

$1\leq t\leq10$
$3\leq n\leq1000$
$1\leq A[i]\leq n$
$A_{sorted}=$ integers that increment by $\mbox{1}$ from $\mbox{1}$ to $n$

Output Format

For each test case, print YES if $\mbox{A}$ can be fully sorted.  Otherwise, print NO.

Sample Input
3
3
3 1 2
4
1 3 4 2
5
1 2 3 5 4

Sample Output
YES
YES
NO

Explanation

In the explanation below, the subscript of $\mbox{A}$ denotes the number of operations performed.

Test Case 0: 

$A_0=\{3,1,2\}\to\text{rotate}(3,1,2)\to A_1=\{1,2,3\}$ 

$\mbox{A}$ is now sorted, so we print $\textbf{YES}$ on a new line.

Test Case 1: 

$A_0=\{1,3,4,2\}\to\text{rotate}(3,4,2)\to A_1=\{1,4,2,3\}$. 

$A_1=\{1,4,2,3\}\to\text{rotate}(4,2,3)\to A_2=\{1,2,3,4\}$. 

$\mbox{A}$ is now sorted, so we print $\textbf{YES}$ on a new line.

Test Case 2:

No sequence of rotations will result in a sorted $\mbox{A}$. Thus, we print $\boldsymbol{\textbf{NO}}$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Implementation


Solutions:
import copy
t = int(input())
for z in range(t):
	input()
	realList = [int(n) for n in input().split()]
	sortedList = copy.copy(realList)
	sortedList.sort()
	listLen = len(sortedList)
	for i in range(listLen - 2):
		if realList[i] == sortedList[i]:
			continue
		myInd = realList.index(sortedList[i])
		while myInd > i:
			if myInd == listLen - 1:
				temp = realList[myInd - 2]
				realList[myInd - 2] = realList[myInd - 1]
				realList[myInd - 1] = realList[myInd]
				realList[myInd] = temp
			else:
				temp = realList[myInd - 1]
				realList[myInd - 1] = realList[myInd]
				realList[myInd] = realList[myInd + 1]
				realList[myInd + 1] = temp
			myInd -= 1
	if realList[listLen - 1] == sortedList[listLen - 1]:
		print('YES')
	else:
		print('NO')


t = int(input())

def cansort(a, i):
	if i == 2:
		return a[1] == (a[0] + 1) % 3
	ind = a.index(i)
	while ind < i - 1:
		if ind < i - 2:
			(a[ind], a[ind + 1], a[ind + 2]) = (a[ind + 1], a[ind + 2], a[ind])
			ind = ind + 2
		else:
			(a[ind - 1], a[ind], a[ind + 1]) = (a[ind + 1], a[ind - 1], a[ind])
			ind = ind + 1
	return cansort(a, i - 1)
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print('YES' if cansort(a, n) else 'NO')


def rotate(arr, a):
	s = sorted(arr[a:a + 3])
	for i in range(3):
		if arr[a] == s[0]:
			return True
		(arr[a], arr[a + 1], arr[a + 2]) = (arr[a + 2], arr[a], arr[a + 1])
	return False
n = int(input())
for loop in range(n):
	N = int(input())
	A = list(map(int, input().split(' ')))
	sortedA = sorted(A)
	for y in range(len(A)):
		for x in range(len(A) - 2):
			rotate(A, x)
	print('YES' if sortedA == A else 'NO')


t = int(input().strip())

def rotate(a, i):
	if i < 0:
		return 0
	(n0, n1, n2) = a[i:i + 3]
	a[i] = n2
	a[i + 1] = n0
	a[i + 2] = n1
for i in range(t):
	n = int(input().strip())
	a = [int(s) for s in input().strip().split(' ')]
	for num in range(n, 0, -1):
		dest_i = num - 1
		i = a.index(num)
		for current_index in range(i, dest_i):
			if current_index == 0:
				rotate(a, 0)
			else:
				rotate(a, current_index - 1)
	ordered = True
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ordered = False
			break
	if ordered:
		print('YES')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline())
for t in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	if len(A) <= 2:
		print('NO')
		continue
	while True:
		last_rotation = None
		for i in range(len(A) - 2):
			if A[i] > max(A[i + 1], A[i + 2]):
				A[i:i + 3] = (A[i + 1], A[i + 2], A[i])
				last_rotation = i
			elif A[i + 1] > max(A[i], A[i + 2]):
				A[i:i + 3] = (A[i + 2], A[i], A[i + 1])
				last_rotation = i
		if not last_rotation:
			print('YES')
			break
		if last_rotation < 2:
			if A[1] < min(A[0], A[2]):
				A[:3] = (A[1], A[2], A[0])
			elif A[2] < min(A[0], A[1]):
				A[:3] = (A[2], A[0], A[1])
			if A[1] < A[2]:
				print('YES')
			else:
				print('NO')
			break


import sys
import copy

def sort_possible(array):
	array_copy = copy.copy(array)
	if len(array) != 3:
		return array
	else:
		s_possible = False
		while True:
			array_copy = array_copy[1:] + array_copy[:1]
			if min(array_copy) == array_copy[0]:
				break
			else:
				continue
		return array_copy

def sorted(array):
	if len(array) != 3:
		return False
	elif array[0] <= array[1] <= array[2]:
		return True
	else:
		return False
t = int(input().strip())
for tests in range(0, t):
	length = int(input().strip())
	array = [int(i) for i in input().strip().split(' ')]
	ori_array = copy.copy(array)
	ori_array.sort()
	output = 'NO'
	while True:
		temp_array = copy.copy(array)
		for index in range(0, length):
			s = array[index:index + 3]
			if len(s) == 3:
				so = sorted(s)
				if so:
					continue
				else:
					new_array = sort_possible(array[index:index + 3])
					array[index:index + 3] = new_array
			else:
				continue
		if ori_array == array:
			output = 'YES'
			break
		elif temp_array == array:
			output = 'NO'
			break
		else:
			continue
	print(output)


t = int(input())
for case in range(t):
	n = int(input())
	list_in = [int(i) for i in input().split(sep=' ')]
	list_sort = [i for i in range(1, n + 1)]
	status = True
	while list_in != list_sort:
		for ind in range(len(list_in) - 2):
			n0 = list_in[ind]
			n1 = list_in[ind + 1]
			n2 = list_in[ind + 2]
			least = min(n0, n2, n1)
			if n0 == least:
				continue
			elif n1 == least:
				list_in[ind] = n1
				list_in[ind + 1] = n2
				list_in[ind + 2] = n0
			elif n2 == least:
				list_in[ind] = n2
				list_in[ind + 1] = n0
				list_in[ind + 2] = n1
		if list_in[:n - 2] == list_sort[:n - 2]:
			if list_in[n - 1] == n - 1 and list_in[n - 2] == n:
				print('NO')
				break
			elif list_in[n - 1] == n and list_in[n - 2] == n - 1:
				print('YES')
				break


import sys

def isSorted(arr):
	n = len(arr)
	last = arr[n - 1]
	sorted = True
	for i in range(n - 2):
		if arr[i] > arr[i + 1] or arr[i] > last:
			sorted = False
			break
	return sorted

def doRotate(arr, index):
	n = len(arr)
	leftI = 0
	if index + 2 <= n - 1:
		tmp = arr[index]
		arr[index] = arr[index + 1]
		arr[index + 1] = arr[index + 2]
		arr[index + 2] = tmp
		leftI = index - 1 if index > 0 else index
	else:
		tmp = arr[index - 1]
		arr[index - 1] = arr[index]
		arr[index] = arr[index + 1]
		arr[index + 1] = tmp
		leftI = index - 2 if index - 2 > 0 else index - 2
	return leftI

def doSort(arr):
	n = len(arr)
	i = 0
	while i < n - 1:
		if arr[i] > arr[i + 1]:
			if i == n - 2 and isSorted(arr):
				return False
			else:
				i = doRotate(arr, i)
		else:
			i = i + 1
	return True
T = int(input().strip())
for tc in range(T):
	n = input()
	arr = [int(i) for i in input().strip().split()]
	if doSort(arr):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	input()
	l = list(map(int, input().split()))
	for _ in range(len(l)):
		for i in range(len(l) - 3 + 1):
			if l[i] > l[i + 1] and l[i] > l[i + 2]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
				(l[i + 1], l[i + 2]) = (l[i + 2], l[i + 1])
			elif l[i] < l[i + 1] and l[i] > l[i + 2]:
				(l[i], l[i + 2]) = (l[i + 2], l[i])
				(l[i + 1], l[i + 2]) = (l[i + 2], l[i + 1])
			elif l[i] > l[i + 1] and l[i] < l[i + 2]:
				(l[i], l[i + 1]) = (l[i + 1], l[i])
				(l[i + 1], l[i + 2]) = (l[i + 2], l[i + 1])
	if any((l[i] > l[i + 1] for i in range(len(l) - 1))):
		print('NO')
	else:
		print('YES')


GOOD = set(['123', '231', '312'])

def find_max(A):
	max_val = 0
	max_ind = -1
	for (i, k) in enumerate(A):
		if k > max_val:
			max_val = k
			max_ind = i
	return (max_ind, max_val)

def move_max_to_right(A):
	(ind, val) = find_max(A)
	while A[-1] < val:
		(A[ind - 1], A[ind], A[ind + 1]) = (A[ind + 1], A[ind - 1], A[ind])
		ind = ind + 1
	return A

def solve(A):
	len_a = len(A)
	for step in range(len_a - 3):
		A = move_max_to_right(A[0:len_a - step])
	s = str(A[0]) + str(A[1]) + str(A[2])
	return 'YES' if s in GOOD else 'NO'
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve(A))


__author__ = 'sunghyo.jung'
for t in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	for i in range(n - 2):
		min_value = min(a[i:])
		min_idx = -1
		for j in range(i, n):
			if a[j] == min_value:
				min_idx = j
				break
		while min_idx > i + 2:
			a[min_idx - 2:min_idx + 1] = a[min_idx - 1:min_idx + 1] + a[min_idx - 2:min_idx - 1]
			min_idx -= 1
		while min_idx != i:
			a[i:i + 3] = a[i + 1:i + 3] + a[i:i + 1]
			min_idx -= 1
	print('YES' if a[n - 3:n] == sorted(a[n - 3:n]) else 'NO')


def check(arr):
	l = len(arr)
	total = 0
	for i in range(l):
		inversion = 0
		for j in range(i, l):
			if arr[i] > arr[j]:
				inversion += 1
		total += inversion
	return 'YES' if total % 2 == 0 else 'NO'
t = int(input().strip())
for at in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split(' ')))
	print(check(arr))


t = int(input())
for test in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	arr_ind = arr.copy()
	tran_count = 0
	order = 0
	for i in range(n):
		if arr_ind[i] != 0:
			value = arr[arr[i] - 1]
			arr_ind[i] = 0
			arr_ind[arr[i] - 1] = 0
			while value != arr[i]:
				tran_count += 1
				arr_ind[value - 1] = 0
				value = arr[value - 1]
	if tran_count % 2 == 0:
		print('YES')
	else:
		print('NO')


def rotate_all(A):
	S = sorted(A)
	s = 0
	l = len(A)
	while l > 2:
		m = S[s]
		i = A.index(m)
		if i == 0:
			A = A[1:]
		elif i == l - 1:
			if l - 3 > 0:
				A = [A[l - 3]] + A[:l - 3] + [A[l - 2]]
			else:
				A = [A[l - 3]] + [A[l - 2]]
		else:
			A = [A[i + 1]] + A[:i] + A[i + 2:]
		s += 1
		l -= 1
	if A[1] > A[0]:
		return 'YES'
	else:
		return 'NO'
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(rotate_all(A))


def isSorted(arr, start, end):
	for i in range(start, end):
		if arr[i] > arr[i + 1]:
			return False
	return True

def canWeSort(arr, start, end):
	if end - start + 1 <= 2:
		return isSorted(arr, start, end)
	if arr[start] == start + 1:
		return canWeSort(arr, start + 1, end)
	ind = arr.index(start + 1)
	while ind - start + 1 > 3:
		temp = arr[ind - 2]
		arr[ind - 2] = arr[ind - 1]
		arr[ind - 1] = arr[ind]
		arr[ind] = temp
		ind = ind - 1
	if ind == start + 2:
		temp = arr[ind - 1]
		arr[ind - 1] = arr[ind - 2]
		arr[ind - 2] = arr[ind]
		arr[ind] = temp
	else:
		temp = arr[ind - 1]
		arr[ind - 1] = arr[ind]
		arr[ind] = arr[ind + 1]
		arr[ind + 1] = temp
	return canWeSort(arr, start + 1, end)
T = int(input())
for i in range(T):
	N = int(input())
	arr = [int(val) for val in input().split(' ')]
	result = canWeSort(arr, 0, N - 1)
	if result:
		print('YES')
	else:
		print('NO')


T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	a = [int(i) for i in input().strip().split(' ')]
	count = 0
	for i in range(N):
		for j in range(i, N):
			if a[i] > a[j]:
				count += 1
	if count % 2 == 1:
		print('NO')
	else:
		print('YES')


def check_sort(arr):
	inversions = 0
	for i in range(len(arr) - 1):
		for j in range(i + 1, len(arr)):
			if arr[i] > arr[j]:
				inversions += 1
	if inversions % 2 == 0:
		return 'YES'
	return 'NO'
for i in range(int(input().strip())):
	input()
	arr = [int(i) for i in input().strip().split(' ')]
	print(check_sort(arr))


import sys

def canSort(l):
	s = sorted(l)
	for i in s[:-2]:
		if l.index(i) % 2:
			l.remove(i)
			(l[0], l[1]) = (l[1], l[0])
		else:
			l.remove(i)
	if l[0] < l[1]:
		return True
	else:
		return False
t = int(sys.stdin.readline().strip())
for _ in range(t):
	n = int(sys.stdin.readline().strip())
	A = list(map(int, sys.stdin.readline().split()))
	if canSort(A):
		print('YES')
	else:
		print('NO')


t = int(input())
import sys

def swp(l, i):
	tmp = l[i]
	l[i] = l[i + 1]
	l[i + 1] = l[i + 2]
	l[i + 2] = tmp

def is_sorted(l):
	for i in range(1, len(l)):
		if l[i] < l[i - 1]:
			return False
	return True
for _ in range(t):
	input()
	l = list(map(int, input().split()))
	l.insert(0, 0)
	for i in range(len(l) - 2):
		index = l.index(i)
		if i != index:
			for j in range(index - i):
				if index - j - 1 + 2 == len(l):
					swp(l, index - j - 1 - 1)
				else:
					swp(l, index - j - 1)
	if is_sorted(l):
		print('YES')
	else:
		print('NO')


import sys
data = sys.stdin.readlines()
T = int(data[0].rstrip('\n'))
del data[0]

def rotate(A, i):
	a = A[i]
	b = A[i + 1]
	c = A[i + 2]
	A[i] = b
	A[i + 1] = c
	A[i + 2] = a
	return A
for i in range(T):
	N = int(data[2 * i].rstrip('\n'))
	A = [int(v) for v in data[2 * i + 1].rstrip('\n').split(' ')]
	rots = 0
	for j in range(N):
		for k in range(j + 1, N):
			if A[j] > A[k]:
				rots += 1
	if rots & 1:
		print('NO')
	else:
		print('YES')


n = int(input().strip())
for tests in range(n):
	n = int(input().strip())
	num = [int(x) for x in input().strip().split(' ')]
	i = 0
	swapping = True
	while swapping:
		swapping = False
		for i in range(n - 2):
			if num[i] > num[i + 1]:
				temp = num[i]
				num[i] = num[i + 1]
				num[i + 1] = num[i + 2]
				num[i + 2] = temp
				swapping = True
	abc = num[len(num) - 3] <= num[len(num) - 2] <= num[len(num) - 1]
	bca = num[len(num) - 2] <= num[len(num) - 1] <= num[len(num) - 3]
	cab = num[len(num) - 1] <= num[len(num) - 3] <= num[len(num) - 2]
	if abc or bca or cab:
		print('YES')
	else:
		print('NO')


j = int(input())
for h in range(j):
	a = int(input())
	l = list(map(int, input().split()))
	u = 'no'
	flag = 0
	k = sorted(l)
	i = 0
	while i < a - 1:
		j = i
		if flag != 1:
			while k[i] != l[j]:
				j = j + 1
			while i != j:
				if j == i + 1:
					if j == a - 1:
						flag = 1
						break
					temp = l[j - 1]
					temp1 = l[j]
					l[j] = l[j + 1]
					l[j + 1] = temp
					l[j - 1] = temp1
					j = j - 1
				else:
					temp = l[j]
					temp1 = l[j - 1]
					l[j] = temp1
					l[j - 1] = l[j - 2]
					l[j - 2] = temp
					j = j - 2
			i = i + 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


import sys

def rotate(s, initial):
	if min(s) == s[0]:
		return s
	else:
		s.append(s[0])
		s = s[1:]
		return rotate(s, initial)

def sort2(n, array):
	if array == sorted(array):
		return 'YES'
	else:
		for j in range(n):
			s = []
			try:
				s.append(array[j])
				s.append(array[j + 1])
				s.append(array[j + 2])
				try:
					s = rotate(s, s)
				except RuntimeError:
					pass
				array[j] = s[0]
				array[j + 1] = s[1]
				array[j + 2] = s[2]
			except IndexError:
				pass
		return sort2(n, array)

def sort(n, array):
	count = 0
	while array != sorted(array):
		count += 1
		if count == n:
			break
		for j in range(n):
			s = []
			try:
				s.append(array[j])
				s.append(array[j + 1])
				s.append(array[j + 2])
				try:
					s = rotate(s, s)
				except RuntimeError:
					pass
				array[j] = s[0]
				array[j + 1] = s[1]
				array[j + 2] = s[2]
			except IndexError:
				pass
	if array == sorted(array):
		return 'YES'
	else:
		return 'NO'
t = int(input().strip())
temp = []
for a0 in range(t):
	n = input().strip()
	n = int(n)
	array = input().strip().split(' ')
	array = [int(i) for i in array]
	temp.append([n, array])
for i in temp:
	print(sort(i[0], i[1]))


def permParity(A, N):
	parity = 0
	for i in range(0, N):
		idx = A.index(i + 1)
		if idx != i:
			parity += 1
			a = A[i]
			A[i] = i + 1
			A[idx] = a
	if parity % 2 == 0:
		return 'YES'
	return 'NO'
T = input()
for i in range(0, int(T)):
	N = input().strip().split(' ')
	N = int(N[0])
	A = input().strip().split(' ')
	A = [int(a) for a in A]
	print(permParity(A, N))


import sys
num_cases = int(sys.stdin.readline().strip())

def swap(array, i1, i2):
	tmp = array[i1]
	array[i1] = array[i2]
	array[i2] = tmp

def move_left(array, current_index, distance_to_move):
	if distance_to_move == 0:
		return
	elif distance_to_move > 2:
		move_left(array, current_index, 2)
		move_left(array, current_index - 2, distance_to_move - 2)
	elif distance_to_move == 1:
		swap(array, current_index, current_index - 1)
		swap(array, current_index, current_index + 1)
	else:
		swap(array, current_index, current_index - 2)
		swap(array, current_index, current_index - 1)

def move(element, current_index, array):
	distance_to_move = current_index - element + 1
	move_left(array, current_index, distance_to_move)

def test(array):
	possible = True
	for i in range(len(array) - 1):
		expected_element = i + 1
		if array[i] != expected_element and i == len(array) - 2:
			possible = False
		elif array[i] != expected_element:
			current_index = array.index(expected_element)
			move(expected_element, current_index, array)
	if possible:
		return 'YES'
	return 'NO'
for case in range(num_cases):
	size = sys.stdin.readline()
	array = [int(x) for x in sys.stdin.readline().strip().split()]
	print(test(array))


def put_order(a, b, c):
	if b < c < a:
		return (b, c, a)
	elif c < a < b:
		return (c, a, b)
	elif b < a and b < c:
		return (b, c, a)
	elif c < a and c < b:
		return (c, a, b)
	else:
		return (a, b, c)

def answer(n, a):
	for j in range(n):
		for i in range(1, n - 1):
			if a[i - 1] > a[i] or a[i] > a[i + 1]:
				ordered = put_order(a[i - 1], a[i], a[i + 1])
				a[i - 1] = ordered[0]
				a[i] = ordered[1]
				a[i + 1] = ordered[2]
		if sorted(a) == a:
			break
	return 'YES' if sorted(a) == a else 'NO'
t = int(input().strip())
for t_i in range(t):
	n = int(input().strip())
	a = [int(ai) for ai in input().strip().split(' ')]
	print(answer(n, a))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 3):
		target_num = i + 1
		if a[i] == target_num:
			continue
		j = a.index(target_num)
		if j == n - 1:
			a = a[:-3] + a[-1:] + a[-3:-1]
			j = n - 3
		a = a[:i] + a[j:j + 2] + a[i:j] + a[j + 2:]
	tail = a[-3:]
	if tail[0] < tail[1] < tail[2] or tail[1] < tail[2] < tail[0] or tail[2] < tail[0] < tail[1]:
		print('YES')
	else:
		print('NO')


def inps():
	return [int(get) for get in input().strip().split(' ')]

def rot(l, n, d):
	if d > 1:
		e = d // 2 * 2
		t = l[n]
		for i in range(n, n - e, -1):
			l[i] = l[i - 1]
		l[n - e] = t
		d = d - d // 2 * 2
		n = n - e
	if n < len(l) - 1:
		n = n + 2 - d
	for i in range(d):
		t = l[n]
		l[n] = l[n - 2]
		l[n - 2] = l[n - 1]
		l[n - 1] = t
	return l
t = int(input().strip())
for case in range(t):
	n = int(input().strip())
	l = inps()
	sl = sorted(l)
	for i in sl:
		d = l.index(i) - sl.index(i)
		l = rot(l, l.index(i), d)
	print('YES') if l == sl else print('NO')


import sys
t = int(input().strip())
for qq in range(0, t):
	n = int(input().strip())
	b = input().strip().split(' ')
	a = []
	for i in b:
		a.append(int(i))
	k = 1
	while k - 1 != n - 2:
		while a[k - 1] == k and k - 1 < n - 2:
			k += 1
		for i in range(k - 1, n - 2):
			for j in range(i, i + 2):
				if a[i + 1] == min(a[i], a[i + 1], a[i + 2]):
					(a[i], a[i + 1], a[i + 2]) = (a[i + 1], a[i + 2], a[i])
				elif a[i + 2] == min(a[i], a[i + 1], a[i + 2]):
					(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])
	if a[n - 2] < a[n - 1]:
		print('YES')
	else:
		print('NO')


n = int(input())

def inOrder(l):
	return all((l[i] <= l[i + 1] for i in xrange(len(l) - 1)))
for _ in range(n):
	l = int(input())
	arr = list(map(int, input().split()))
	disorder_count = 0
	for x in range(l):
		for y in range(x, l):
			if arr[x] > arr[y]:
				disorder_count += 1
	if disorder_count % 2 == 0:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	out = 0
	for j in range(len(a)):
		temp = sum((1 for k in a[j + 1:] if k < a[j]))
		out = out + temp
	if out % 2 == 0:
		print('YES')
	else:
		print('NO')


def rotate(lst, i, min_affected):
	if i == 0:
		return True
	if i < len(lst) - 1 and i - 1 >= min_affected:
		(lst[i - 1], lst[i], lst[i + 1]) = (lst[i], lst[i + 1], lst[i - 1])
		return True
	elif i - 2 >= min_affected:
		(lst[i - 2], lst[i - 1], lst[i]) = (lst[i - 1], lst[i], lst[i - 2])
		return True
	return False
T = int(input())
for t in range(T):
	N = int(input())
	lst = [int(k) for k in input().strip().split()]
	can_order = True
	for (i, el) in enumerate(sorted(lst)):
		pos = lst.index(el)
		for rt in range(pos - i):
			if not rotate(lst, pos, i):
				can_order = False
				break
			pos -= 1
		if not can_order:
			break
	print('YES' if can_order else 'NO')


def count_inversions(array):
	s = set()
	n = len(array)
	for (i, num) in enumerate(array):
		j = i + 1
		while j < n:
			if array[j] < num:
				s.add((num, array[j]))
			j += 1
	return len(s)
t = int(input().strip())
for _ in range(t):
	N = int(input())
	A = list(map(int, input().split()))
	inversions = count_inversions(A)
	print('NO' if inversions % 2 == 1 else 'YES')


import sys
t = int(input().strip())
for i in range(0, t):
	n = int(input().strip())
	a = [int(a_temp) for a_temp in input().strip().split(' ')]
	location_map = [0] * (n + 1)
	for i in range(0, n):
		location_map[a[i]] = i
	count_perm = 0
	for i in range(0, n):
		if a[i] != i + 1:
			temp = a[i]
			a[i] = a[location_map[i + 1]]
			a[location_map[i + 1]] = temp
			count_perm += 1
			location_map[temp] = location_map[i + 1]
			location_map[a[i]] = i
	if count_perm % 2 == 0:
		print('YES')
	else:
		print('NO')


def bubble(triple, i):
	if i == 0:
		(triple[0], triple[1]) = (triple[1], triple[0])
		(triple[1], triple[2]) = (triple[2], triple[1])
	elif i == 1:
		(triple[0], triple[2]) = (triple[2], triple[0])
		(triple[1], triple[2]) = (triple[2], triple[1])
	return triple

def robot_sort(xs):
	xs = xs[:]
	unsorted = len(xs)
	while unsorted >= 3:
		i = xs.index(max(xs[:unsorted]))
		while i != unsorted - 1:
			if abs(unsorted - i + 1) % 2 == 0:
				if i + 1 == unsorted:
					continue
				else:
					xs[i:i + 3] = bubble(xs[i:i + 3], 0)
					i += 2
			elif i == 0:
				xs[i:i + 3] = bubble(xs[i:i + 3], 0)
				i += 2
			else:
				xs[i - 1:i + 2] = bubble(xs[i - 1:i + 2], 1)
				i += 1
		unsorted -= 1
	return xs
n = int(input())
for _ in range(n):
	size = int(input())
	xs = list(map(int, input().split(' ')))
	robot_sorted = robot_sort(xs)
	if all((robot_sorted[i] <= robot_sorted[i + 1] for i in range(size - 1))):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[j] < a[i]:
				sum += 1
	print('YES' if sum % 2 == 0 else 'NO')


def parity(A):
	visited = [False] * len(A)
	start = 0
	par = 0
	while start < len(A):
		current = start
		length = 0
		while visited[current] == False:
			visited[current] = True
			current = A[current]
			length += 1
		while start < len(A) and visited[start] == True:
			start += 1
		par += (length - 1) % 2
		par %= 2
	return par
T = int(input())
for t in range(T):
	N = int(input())
	A = [int(a) - 1 for a in input().split()]
	if parity(A) == 0:
		print('YES')
	else:
		print('NO')


import sys
T = int(input().strip())

def parity(permList):
	if len(permList) == 1:
		return 0
	else:
		numInversion = len(permList) - permList.index(max(permList)) - 1
		permList.remove(max(permList))
		return numInversion + parity(permList)
for t0 in range(T):
	n = input()
	a = [int(i) for i in input().split(' ')]
	print('YES') if parity(a) % 2 == 0 else print('NO')


def rotate(i, arr):
	if i + 2 >= len(arr):
		return
	while arr[i] > arr[i + 1] or arr[i] > arr[i + 2]:
		(arr[i], arr[i + 1], arr[i + 2]) = (arr[i + 1], arr[i + 2], arr[i])
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	a = [int(x) for x in input().strip().split()]
	for i in range(len(a)):
		for j in range(len(a)):
			rotate(j, a)
	if a == sorted(a):
		print('YES')
	else:
		print('NO')


import sys

def rotate(arr):
	res = arr[:]
	res[0] = arr[1]
	res[1] = arr[2]
	res[2] = arr[0]
	return res

def is_sorted(arr):
	tmp = list(arr)
	tmp = sorted(tmp)
	if tmp == arr:
		return True
	return False

def one_iteration(arr):
	i = 0
	k = len(arr) - 1
	for i in range(k):
		if arr[i] > arr[i + 1]:
			if i == k - 1:
				j = i - 1
			else:
				j = i
			t = arr[j:j + 3]
			t1 = rotate(t)
			arr[j] = t1[0]
			arr[j + 1] = t1[1]
			arr[j + 2] = t1[2]
	return arr

def attempt(arr, i, k):
	res = False
	res_arr = arr[:]
	if is_sorted(arr):
		res = True
	elif i >= k:
		res = False
	else:
		res_arr = one_iteration(arr)
		if is_sorted(res_arr):
			res = True
	return (res, res_arr)

def is_sortable(arr):
	k = len(arr)
	res = False
	t = arr[:]
	for i in range(2 * k):
		(res, t) = attempt(t, i, k)
		if res:
			break
	return res
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split(' ')]
	res = is_sortable(arr)
	if res == True:
		print('YES')
	else:
		print('NO')


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	arr = [int(val) for val in input().strip().split(' ')]
	parity = 0
	for indx in range(n - 1):
		for indx2 in range(indx + 1, n):
			if arr[indx] > arr[indx2]:
				parity = parity + 1
	print('YES') if parity % 2 == 0 else print('NO')


t = int(input().strip())
for case in range(t):
	n = int(input().strip())
	list = [int(val) for val in input().strip().split()]
	inversions = 0
	for curr in range(len(list)):
		for num in list[curr + 1:]:
			if num < list[curr]:
				inversions += 1
	print('YES' if inversions % 2 == 0 else 'NO')


import itertools

def inversion_number(A):
	return sum((1 for (x, y) in itertools.combinations(range(len(A)), 2) if A[x] > A[y]))
t = int(input())
for _ in range(t):
	input()
	i = list(map(int, input().split(' ')))
	if inversion_number(i) % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	_ = input()
	arr = [int(x) for x in input().split()]
	swaps = 0
	for (i, n) in enumerate(arr):
		swaps += sum([1 for m in arr[i + 1:] if n > m])
	if swaps % 2 == 0:
		print('YES')
	else:
		print('NO')


def check(A):
	for j in range(len(A) - 2):
		for i in range(len(A) - 2):
			if (A[i + 2] < A[i]) & (A[i + 2] < A[i + 1]):
				temp1 = A[i + 1]
				temp2 = A[i + 2]
				A[i + 1] = A[i]
				A[i + 2] = temp1
				A[i] = temp2
			elif A[i] > A[i + 1] & A[i + 1] < A[i + 2]:
				temp1 = A[i + 1]
				temp2 = A[i + 2]
				A[i + 2] = A[i]
				A[i] = temp1
				A[i + 1] = temp2
	if A == sorted(A):
		print('YES')
	else:
		print('NO')
t = int(input())
while t > 0:
	a = int(input())
	c = [int(x) for x in input().split()]
	check(c)
	t = t - 1


t = int(input().strip())

def check_sorted(lst):
	srted = False
	n = 0
	while not srted:
		if n >= len(lst) - 1:
			return True
		if lst[n] > lst[n + 1]:
			return False
		n += 1
for _ in range(t):
	l = int(input().strip())
	arr = [int(c) for c in input().strip().split(' ')]
	arr_sorted = False
	while not arr_sorted:
		prev_arr = arr[:]
		arr_sorted = check_sorted(arr)
		for n in range(l - 2):
			while arr[n] != min(arr[n:n + 3]):
				chunk = arr[n:n + 3]
				chunk.append(chunk[0])
				chunk.pop(0)
				arr[n:n + 3] = chunk
		if arr == prev_arr:
			break
	if arr_sorted:
		print('YES')
	else:
		print('NO')


import sys, copy

def checkSort(arr):
	arr_sort = copy.copy(arr)
	arr_sort.sort()
	L = len(arr_sort)
	for x in range(L - 2):
		if arr[x] != arr_sort[x]:
			ind = arr.index(arr_sort[x])
			while ind > x:
				if ind == L - 1:
					t = arr[ind - 2]
					arr[ind - 2] = arr[ind - 1]
					arr[ind - 1] = arr[ind]
					arr[ind] = t
				else:
					t = arr[ind - 1]
					arr[ind - 1] = arr[ind]
					arr[ind] = arr[ind + 1]
					arr[ind + 1] = t
				ind -= 1
	if arr[L - 1] == arr_sort[L - 1]:
		print('YES')
	else:
		print('NO')
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	arr = list(map(int, sys.stdin.readline().split()))
	checkSort(arr)


from sys import stdin
num = int(stdin.readline())
for n in range(num):
	t = int(stdin.readline())
	a = stdin.readline().split()
	count = 0
	for i in range(t):
		for j in range(i + 1, t):
			if int(a[i]) > int(a[j]):
				count += 1
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')


def rotate(a, p):
	temp = a[p]
	a[p] = a[p + 1]
	a[p + 1] = a[p + 2]
	a[p + 2] = temp

def is_valid(a, p):
	count = 0
	for i in range(2):
		if a[p + i] < a[p + i + 1]:
			count += 1
		else:
			count -= 1
	if a[p + 2] < a[p]:
		count += 1
	else:
		count -= 1
	if count != 1:
		return False
	else:
		return True
T = int(input().strip())
for t in range(T):
	n = int(input().strip())
	arr = [int(a) for a in input().strip().split(' ')]
	p = 0
	stop = False
	while p >= 0 and p < len(arr) - 1 and (not stop):
		if arr[p] > arr[p + 1]:
			if p + 2 == len(arr):
				if is_valid(arr, p - 1):
					rotate(arr, p - 1)
					p -= 1
					p = max(p, 0)
				else:
					stop = True
			else:
				rotate(arr, p)
				p -= 1
				p = max(p, 0)
		else:
			p += 1
	if not stop:
		print('YES')
	else:
		print('NO')


tests = int(input())

def solve(arr):
	ans = []
	i = 0
	while i < len(arr) - 2:
		m = min(arr[i:])
		index = arr.index(m)
		while index > i:
			if index - 2 >= i:
				(arr[index - 2], arr[index - 1], arr[index]) = (arr[index], arr[index - 2], arr[index - 1])
				index -= 2
			elif index - 1 >= i:
				(arr[index - 1], arr[index], arr[index + 1]) = (arr[index], arr[index + 1], arr[index - 1])
				index -= 1
		i += 1
	if arr[-2] > arr[-1]:
		print('NO')
	else:
		print('YES')
test = 1
while test <= tests:
	l = int(input())
	arr = list(map(int, input().split(' ')))
	solve(arr)
	test += 1


t = int(input())
for case in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	inversions = 0
	for i in range(1, n):
		for j in range(0, i):
			if a[i] < a[j]:
				inversions += 1
	if inversions % 2 == 0:
		print('YES')
	else:
		print('NO')


for a0 in range(int(input())):
	n = int(input())
	A = [int(temp) for temp in input().split()]
	ans = sorted(A)
	x = 0
	while x < n - 2 and A != ans:
		for i in range(n - 2 - x):
			three = A[i:i + 3]
			for j in range((1 + three.index(max(three))) % 3):
				temp = A[i]
				A[i] = A[i + 1]
				A[i + 1] = A[i + 2]
				A[i + 2] = temp
		x += 1
	if A == ans:
		print('YES')
	else:
		print('NO')


T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	arr = list(map(int, input().strip().split()))
	s_arr = sorted(arr)
	parity = 1
	for i in range(0, len(arr) - 1):
		if arr[i] != s_arr[i]:
			parity *= -1
			mn = min(range(i, len(arr)), key=arr.__getitem__)
			(arr[i], arr[mn]) = (arr[mn], arr[i])
	if parity == 1:
		print('YES')
	else:
		print('NO')


def sortable(arr):
	sorted_arr = sorted(arr)
	parity = 0
	for i in range(0, len(sorted_arr)):
		num = sorted_arr[i]
		idx = arr.index(num)
		n = i - idx
		nswaps(n, arr, idx)
		parity += n
	if parity % 2 == 0:
		return 'YES'
	return 'NO'

def nswaps(n, arr, start):
	add = -1 if n < 0 else 1
	for i in range(start, start + n, add):
		next_i = (i + add) % len(arr)
		(arr[i], arr[next_i]) = (arr[next_i], arr[i])
t = int(input())
for i in range(0, t):
	length = int(input())
	arr = [int(num) for num in input().split(' ')]
	print(sortable(arr))


t = int(input().strip())

def rotate(a, i):
	if i < 0:
		return 0
	(n0, n1, n2) = a[i:i + 3]
	a[i] = n2
	a[i + 1] = n0
	a[i + 2] = n1
for i in range(t):
	n = int(input().strip())
	a = [int(s) for s in input().strip().split(' ')]
	for num in range(n, 0, -1):
		dest_i = num - 1
		i = a.index(num)
		for current_index in range(i, dest_i):
			if current_index == 0:
				rotate(a, 0)
			else:
				rotate(a, current_index - 1)
	ordered = True
	for i in range(n - 1):
		if a[i] > a[i + 1]:
			ordered = False
			break
	if ordered:
		print('YES')
	else:
		print('NO')


T = int(input())
for t in range(T):
	N = int(input())
	numbers = [int(x.strip()) for x in input().split()]
	parity = 0
	for i in range(N - 1):
		target = i + 1
		if numbers[i] != target:
			parity += 1
			swap_index = numbers.index(target)
			(numbers[i], numbers[swap_index]) = (numbers[swap_index], numbers[i])
	print('YES' if parity % 2 == 0 else 'NO')


import sys

def pred(a):
	n = len(a)
	for i in range(n - 2):
		im = a.index(min(a))
		if im % 2 == 0:
			a.pop(im)
		else:
			a.pop(im)
			(a[0], a[1]) = (a[1], a[0])
	return a[0] < a[1]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	if pred(a):
		print('YES')
	else:
		print('NO')


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		arr = ['$']
		arr.extend(list(map(int, input().split())))
		can_sort = True
		for j in range(1, len(arr)):
			while j != arr[j]:
				if j == n - 1 and arr[-1] == n - 1 and (arr[-2] == n):
					can_sort = False
					break
				idx = arr.index(j, j + 1)
				if idx - j >= 2:
					rotate(arr, idx - 2, idx - 1, idx)
				elif idx - j == 1:
					rotate(arr, idx - 1, idx, idx + 1)
					rotate(arr, idx - 1, idx, idx + 1)
			if j == n - 1 and arr[-1] == n - 1 and (arr[-2] == n):
				can_sort = False
				break
		if can_sort == True:
			print('YES')
		else:
			print('NO')

def rotate(arr, a, b, c):
	temp = arr[c]
	arr[c] = arr[b]
	arr[b] = arr[a]
	arr[a] = temp
	return
main()


for T in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	if sum((1 for i in range(N - 1) for j in range(i + 1, N) if A[i] > A[j])) % 2:
		print('NO')
	else:
		print('YES')


nb_tests = int(input())
for i in range(0, nb_tests):
	length = int(input())
	array = [int(x) for x in input().split()]
	inversions = sum((sum((1 for j in range(i + 1, len(array)) if array[j] < array[i])) for i in range(0, len(array))))
	print('YES' if inversions % 2 == 0 else 'NO')


num_tests = int(input().strip())
for _ in range(num_tests):
	length = int(input().strip())
	A = [int(x) for x in input().strip().split()]
	sorted_A = sorted(A)
	tranpositions = 0
	for i in range(len(sorted_A)):
		idx = A.index(sorted_A[i])
		if idx != i:
			temp = A[i]
			A[i] = A[idx]
			A[idx] = temp
			tranpositions += 1
	if tranpositions % 2 == 1:
		print('NO')
	else:
		print('YES')


def is_even_inverse_count(arr, n):
	count = 0
	for (i, v1) in enumerate(arr):
		for v2 in arr[i + 1:]:
			if v1 > v2:
				count += 1
	return count % 2 == 0
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print('YES' if is_even_inverse_count(arr, n) else 'NO')


def sorted(l):
	return all((l[i] <= l[i + 1] for i in range(len(l) - 1)))

def shift(L, l, m, r):
	if l < 0 or m < 0 or r < 0:
		return False
	try:
		(ll, mm, rr) = (L[l], L[m], L[r])
		if L[l] < L[m] and L[l] < L[r]:
			return False
		elif L[m] < L[l] and L[m] < L[r]:
			L[l] = mm
			L[m] = rr
			L[r] = ll
			return True
		elif rr < mm and rr < ll:
			L[l] = rr
			L[m] = ll
			L[r] = mm
			return True
		else:
			return False
	except:
		return False
for t in range(int(input())):
	zz = input()
	a = input()
	ls = list(map(int, a.split()))
	while not sorted(ls):
		action = False
		for i in range(len(ls)):
			ret = shift(ls, i - 1, i, i + 1)
			action = action or ret
		if not action:
			break
	if sorted(ls):
		print('YES')
	else:
		print('NO')


t = int(input().strip())
for i in range(t):
	l = int(input().strip())
	a = [int(r) for r in input().strip().split(' ')]
	count = 0
	for i in range(len(a)):
		for j in range(i, len(a)):
			if a[i] > a[j]:
				count += 1
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')


T = int(input())
for _ in range(T):
	n = int(input())
	L = list(map(int, input().split()))
	l = len(L)
	D = {}
	i = 0
	for _ in L:
		i += 1
		D[_] = 0
		for k in range(i, l):
			if _ > L[k]:
				D[_] += 1
	print('YES' if sum(D.values()) % 2 == 0 else 'NO')


def is_sortable(A):
	mx = A[0]
	count = 0
	for i in range(0, len(A)):
		for j in range(i + 1, len(A)):
			if A[i] > A[j]:
				count += 1
	if count % 2 == 0:
		return 'YES'
	else:
		return 'NO'
T = int(input())
for t_i in range(T):
	(N, A) = (int(input()), [int(x) for x in input().split()])
	print(is_sortable(A))


import sys
t = int(input().strip())
for a in range(t):
	n = int(input().strip())
	arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	count = 0
	for i in range(n):
		count += sum((x < arr[i] for x in arr[i:]))
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')


test_cases = int(input())
for i in range(test_cases):
	length = int(input())
	l = [int(x) for x in input().split()]
	a = 0
	inversions = True
	while a < length:
		b = a + 1
		while b < length:
			inversions ^= l[a] > l[b]
			b += 1
		a += 1
	if inversions:
		print('YES')
	else:
		print('NO')


for a in range(int(input().strip())):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	i = 0
	redo = 0
	while i < n - 2:
		while arr[i] > arr[i + 1] or arr[i] > arr[i + 2]:
			arr.insert(i + 2, arr.pop(i))
			redo = 1
		i += 1
		if i == n - 2 and redo == 1:
			i = 0
			redo = 0
	if arr[n - 2] < arr[n - 1]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	for i in range(n - 2):
		j = a.index(i + 1)
		if j > i:
			del a[j]
			a.insert(i, i + 1)
			if (j - i) % 2 != 0:
				(a[i + 1], a[i + 2]) = (a[i + 2], a[i + 1])
	print('YES' if a[n - 2] + 1 == a[n - 1] else 'NO')


t = int(input())

def get_best_rot(a):
	if a[0] <= a[1] and a[1] <= a[2]:
		return a
	m = min(a)
	score1 = 1000 * a[0] + 100 * a[1] + 10 * a[2]
	score2 = 1000 * a[2] + 100 * a[0] + 10 * a[1]
	score3 = 1000 * a[1] + 100 * a[2] + 10 * a[0]
	m = min(score1, score2, score3)
	if score1 == m:
		return a
	else:
		a.insert(0, a[2])
		del a[-1]
		if score2 == m:
			return a
		else:
			a.insert(0, a[2])
			del a[-1]
			return a
for _ in range(t):
	input()
	arr = [int(i) for i in input().strip().split(' ')]
	for jj in range(len(arr)):
		for i in reversed(range(len(arr) - 2)):
			arr[i:i + 3] = get_best_rot(arr[i:i + 3])
	failed = False
	for i in range(len(arr) - 1):
		if arr[i] > arr[i + 1]:
			failed = True
			break
	if failed:
		print('NO')
	else:
		print('YES')


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	arr = list(map(int, input().strip().split()))
	cnt = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] > arr[j]:
				cnt += 1
	if cnt % 2:
		print('NO')
	else:
		print('YES')


def rotate(arr, i):
	tmp = arr[i]
	arr[i] = arr[i + 1]
	arr[i + 1] = arr[i + 2]
	arr[i + 2] = tmp

def testcase(arr):
	for upto in range(len(arr) - 2, 0, -1):
		for start in range(upto):
			highest = max(arr[start:start + 3])
			if arr[start] == highest:
				rotate(arr, start)
			elif arr[start + 1] == highest:
				rotate(arr, start)
				rotate(arr, start)
			else:
				pass
	if arr[0] < arr[1] < arr[2]:
		print('YES')
	else:
		print('NO')
testcases = int(input().strip())
for t in range(testcases):
	n = int(input().strip())
	arr = [int(x) for x in input().strip().split()]
	testcase(arr)


def solve(lst):
	while len(lst) > 2:
		max_elem = max(lst)
		max_index = lst.index(max_elem)
		reverse_index = len(lst) - max_index - 1
		del lst[max_index]
		if reverse_index % 2 == 1:
			last = lst[-1]
			lst[-1] = lst[-2]
			lst[-2] = last
	if lst[0] < lst[1]:
		return 'YES'
	else:
		return 'NO'
n = int(input())
for i in range(n):
	m = int(input())
	s = input()
	lst = [int(x) for x in s.split(' ')]
	print(solve(lst))


def can_sort(array):
	n = len(array)
	for a in range(1, n - 1):
		index = array.index(a)
		(array[a - 1], array[a:index + 1]) = (a, array[a - 1:index])
		if not (a - index) % 2:
			(array[a], array[a + 1]) = (array[a + 1], array[a])
	return array[n - 2] < array[n - 1]
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(an) for an in input().split()]
	print('YES' if can_sort(A) else 'NO')


T = int(input())
for t in range(T):
	n = int(input())
	arr = [int(x) for x in input().split(' ')]
	ret = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[j] < arr[i]:
				ret += 1
	if ret % 2 == 0:
		print('YES')
	else:
		print('NO')


def Rotate(li, startPos):
	tmps = li[startPos]
	li[startPos] = li[startPos + 1]
	li[startPos + 1] = li[startPos + 2]
	li[startPos + 2] = tmps
for _ in range(int(input())):
	input()
	li = list(map(int, input().split()))
	i = 0
	lastIndex = 0
	for i2 in range(len(li) - 2):
		for i in range(len(li) - 2):
			if li[i + 2] < li[i + 1] and li[i + 2] < li[i]:
				Rotate(li, i)
				Rotate(li, i)
			elif li[i + 1] < li[i + 2] and li[i + 1] < li[i]:
				Rotate(li, i)
	if li[-1] > li[-2] and li[-2] > li[-3]:
		print('YES')
	else:
		print('NO')


t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	a = [int(x) for x in input().strip().split(' ')]
	count = 0
	for j in range(len(a)):
		for k in range(j, len(a)):
			if a[k] < a[j]:
				count += 1
	if count % 2 == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().strip().split()]
	inv = 0
	for i in range(n):
		inv ^= len([a for a in A[i + 1:] if a < A[i]])
	if inv & 1:
		print('NO')
	else:
		print('YES')


def rotate(arr):
	tmp = arr[0]
	arr[0] = arr[1]
	arr[1] = arr[2]
	arr[2] = tmp
	return arr

def main():
	T = int(input())
	for x in range(T):
		arr = []
		for y in range(1):
			n = input()
			arr = list(map(int, input().split(' ')))
			check = True
			s_arr = sorted(arr)
			while arr != s_arr and check:
				for (i, v) in enumerate(arr):
					if i + 3 <= len(arr) and arr[i:i + 3] != sorted(arr[i:i + 3]):
						m = min(arr[i:i + 3])
						while arr[i] != m:
							arr[i:i + 3] = rotate(arr[i:i + 3])
						if arr == s_arr:
							check = False
					if i == len(arr) - 3 and arr[i] == s_arr[i] and (arr[0:i] == s_arr[0:i]):
						check = False
			print('YES' if arr == s_arr else 'NO')
main()


T = int(input())
for T_i in range(T):
	N = int(input())
	A = [int(x) for x in input().split(' ')]
	result = 0
	for i in range(1, N + 1):
		while i != A[0]:
			loc = A.index(i)
			if loc >= 2:
				A.insert(loc - 2, A.pop(loc))
			elif loc == 1:
				A.insert(loc + 1, A.pop(loc - 1))
		del A[0]
		if len(A) == 2 and i + 1 != A[0]:
			result = -1
			break
	if result == 0:
		print('YES')
	else:
		print('NO')


def op(s, i):
	(s[i], s[i + 1], s[i + 2]) = (s[i + 1], s[i + 2], s[i])
t = int(input().strip())
for a0 in range(t):
	n = int(input().strip())
	s = [int(x) for x in input().strip().split(' ')]
	for i in range(-1, n - 3):
		for j in range(n - 3, i, -1):
			if s[j] > s[j + 1]:
				op(s, j)
			if s[j] > s[j + 1]:
				op(s, j)
			if s[j] > s[j + 2]:
				op(s, j)
				op(s, j)
	if s[-1] > s[-2]:
		print('YES')
	else:
		print('NO')


T = int(input().strip())
for dummy in range(T):
	n = int(input().strip())
	a = [int(d) for d in input().strip().split()]
	nSwap = 0
	Done = False
	while not Done:
		Done = True
		for i in range(len(a) - 1):
			if a[i] > a[i + 1]:
				Done = False
				atmp = a[i]
				a[i] = a[i + 1]
				a[i + 1] = atmp
				nSwap += 1
	if nSwap % 2 == 0:
		print('YES')
	else:
		print('NO')


def is_sortable(a):
	n = len(a)
	if n < 3:
		return a[1] > a[0]
	m = a.index(n)
	if (n - 1 - m) % 2 == 0:
		a.pop(m)
		return is_sortable(a)
	elif m > 0:
		(a[m - 1], a[m + 1]) = (a[m + 1], a[m - 1])
		a.pop(m)
		return is_sortable(a)
	else:
		(a[0], a[1], a[2]) = (a[2], a[0], a[1])
		return is_sortable(a)
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split(' ')]
	if is_sortable(a):
		print('YES')
	else:
		print('NO')


t = eval(input())
while t:
	n = eval(input())
	a = [int(x) for x in input().split(' ')]
	i = 0
	while i < n - 3:
		if int(a[i]) != i + 1:
			j = i + 1
			while int(a[j]) != i + 1 and j < n:
				j += 1
			while int(a[i]) != i + 1:
				if j != n - 1:
					first = a[j - 1]
					mid = a[j]
					a[j - 1] = mid
					a[j] = a[j + 1]
					a[j + 1] = first
				else:
					first = a[j - 2]
					mid = a[j - 1]
					a[j - 2] = mid
					a[j - 1] = a[j]
					a[j] = first
				j -= 1
		i += 1
	if a[i + 1] < a[i + 2] and (a[i] < a[i + 1] or a[i] > a[i + 2]) or (a[i + 2] < a[i] and a[i] < a[i + 1]):
		print('YES')
	else:
		print('NO')
	t -= 1


def rotate_left(arr, idx):
	(arr[idx], arr[idx + 1], arr[idx + 2]) = (arr[idx + 1], arr[idx + 2], arr[idx])

def rotate_right(arr, idx):
	(arr[idx], arr[idx + 1], arr[idx + 2]) = (arr[idx + 2], arr[idx], arr[idx + 1])

def is_sorted(arr):
	return sorted(arr) == arr

def can_be_sorted(arr):
	for idx_i in range(len(arr) - 2):
		for idx_j in range(len(arr) - 3, idx_i - 1, -1):
			if arr[idx_j + 1] >= arr[idx_j + 2] <= arr[idx_j]:
				rotate_right(arr, idx_j)
			if arr[idx_j + 2] >= arr[idx_j + 1] <= arr[idx_j]:
				rotate_left(arr, idx_j)
	return 'YES' if is_sorted(arr) else 'NO'
test_count = int(input())
for _ in range(test_count):
	arr_len = input()
	arr = list(map(int, input().split()))
	print(can_be_sorted(arr))


import sys
T = int(input().strip())
for a0 in range(T):
	n = int(input().strip())
	q = [int(q_temp) for q_temp in input().strip().split(' ')]
	parity = 0
	for i in range(len(q)):
		parity += sum((1 for val in q[i + 1:] if val < q[i]))
	if parity % 2 != 0:
		print('NO')
	else:
		print('YES')


from bisect import bisect_left
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	d = 0
	for item in a:
		c = bisect_left(b, item)
		d += c
		if c == len(b):
			b.append(item)
		else:
			b.insert(c, item)
	if (n * (n - 1) // 2 - d) % 2 == 0:
		print('YES')
	else:
		print('NO')


def vector(ls, val):
	count = 0
	for y in ls[:val]:
		if y > ls[val]:
			count += 1
	return count
for _ in range(0, int(input())):
	y = input()
	orij = list(map(lambda x: int(x), input().split()))
	vects = [vector(orij, x) for x in range(0, len(orij))]
	if sum(vects) % 2 == 0:
		print('YES')
	else:
		print('NO')


def isSolvable(arr):
	result = True
	for i in range(len(arr) - 1):
		for j in range(i, len(arr)):
			if arr[i] > arr[j]:
				result = not result
	return result

def main():
	t = int(input().strip())
	for a0 in range(t):
		l = int(input().strip())
		inp = list(map(int, input().strip().split()))
		if isSolvable(inp):
			print('YES')
		else:
			print('NO')
main()


from random import randrange
t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sa = list(reversed(sorted(a)))
	aa = a
	a = list(reversed(a))
	for j in range(n):
		for i in range(n - 2):
			p = a[i:i + 3]
			(z, y, x) = p
			if x == max(p) and x != y:
				a[i] = x
				a[i + 1] = z
				a[i + 2] = y
				if a == sa:
					print('YES')
					break
			elif y == max(p) and y != z:
				a[i] = y
				a[i + 1] = x
				a[i + 2] = z
				if a == sa:
					print('YES')
					break
		else:
			continue
		break
	else:
		print('NO')


times = int(input().strip())

def gprint(stuff):
	pass
for a in range(times):
	gprint('---------------')
	nums = int(input().strip())
	lst = [int(a) for a in input().strip().split(' ')]
	length = len(lst)
	counter = 0
	while counter < length - 3:
		gprint('entered the thing')
		gprint(lst)
		counter += 1
		agadi = lst.index(counter)
		gprint('working for {0}'.format(counter))
		if agadi + 1 == counter:
			gprint('{0} is at the right place'.format(counter))
			continue
		agadi -= -counter - 1
		lst.remove(counter)
		lst.insert(counter - 1, counter)
		if agadi % 2 != 0:
			gprint('swapping')
			temp = lst[counter]
			lst[counter] = lst[counter + 1]
			lst[counter + 1] = temp
		gprint(lst)
	left = lst[-3]
	mid = lst[-2]
	right = lst[-1]
	gprint('left is {0} mid is {1} right is {2}'.format(left, mid, right))
	if mid - left >= 0:
		l = 1
	else:
		l = -1
	r = 1 if mid - right >= 0 else -1
	diff = 1 if right - left >= 0 else -1
	gprint('l,r,diff is {0},{1},{2}'.format(l, r, diff))
	if (l, r, diff) in [(1, 1, -1), (1, -1, 1), (-1, -1, -1)]:
		print('YES')
	else:
		print('NO')


import sys
T = int(input().strip())
for i in range(T):
	n = int(input().strip())
	arr = [int(a) for a in input().strip().split(' ')]
	summ = 0
	for i in range(1, n):
		cnt = 0
		for j in range(i):
			if arr[j] > arr[i]:
				cnt += 1
		summ += cnt
	if summ % 2 == 0:
		print('YES')
	else:
		print('NO')


import sys

def max_pos(a, start, end):
	max_i = start
	for i in range(start + 1, end + 1):
		if a[i] > a[max_i]:
			max_i = i
	return max_i

def shift_left(a, start, by_n):
	for i in range(by_n):
		temp = a[start]
		a[start:start + 2] = a[start + 1:start + 3]
		a[start + 2] = temp

def larrysArray(a):
	n = len(a)
	for dest in range(n - 1, 1, -1):
		group_end = 0
		while group_end < dest:
			group_end = min(group_end + 2, dest)
			m = max_pos(a, group_end - 2, group_end)
			shift_left(a, group_end - 2, 3 - (group_end - m) % 3)
	return a[0] < a[1]
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	a = [int(s) for s in input().strip().split(' ')]
	print('YES' if larrysArray(a) else 'NO')


T = int(input())
for tc in range(T):
	N = int(input())
	A = [int(aa) for aa in input().split(' ')]
	while True:
		i = 0
		while i < len(A) and A[i] == i + 1:
			i += 1
		if i == len(A):
			print('YES')
			break
		if i == len(A) - 2:
			print('NO')
			break
		usortpos = i
		next = i + 1
		i += 1
		while A[i] != next:
			i += 1
		if i + 1 >= len(A):
			i = i - 1
			aa = A[i - 1]
			bb = A[i]
			cc = A[i + 1]
			A[i - 1] = bb
			A[i] = cc
			A[i + 1] = aa
		else:
			aa = A[i]
			bb = A[i + 1]
			del A[i]
			del A[i]
			A.insert(usortpos, aa)
			A.insert(usortpos + 1, bb)


t = int(input())
for penis in range(t):
	size = int(input())
	a = input().split()
	b = []
	for i in a:
		b.append(int(i))
	for i in range(1, len(b) + 1):
		temp = []
		if b[len(b) - 1] == i:
			b[len(b) - 1] = b[len(b) - 2]
			b[len(b) - 2] = b[len(b) - 3]
			b[len(b) - 3] = i
		if b[len(b) - 2] == i:
			b[len(b) - 2] = b[len(b) - 1]
			b[len(b) - 1] = b[len(b) - 3]
			b[len(b) - 3] = i
		for j in range(1, len(b) - 1):
			if b[j - 1] == j and j < i:
				temp.append(b[j - 1])
			if b[j - 1] == i:
				temp.append(b[j - 1])
				temp.append(b[j])
				for k in range(len(b)):
					if k != j - 1 and k != j:
						if i != 1:
							if k > i - 2:
								temp.append(b[k])
						else:
							temp.append(b[k])
		b = temp
	if b[len(b) - 1] == len(b) - 2:
		b[len(b) - 1] = b[len(b) - 2]
		b[len(b) - 2] = b[len(b) - 3]
		b[len(b) - 3] = len(b) - 2
	if b[len(b) - 2] == len(b) - 2:
		b[len(b) - 2] = b[len(b) - 1]
		b[len(b) - 1] = b[len(b) - 3]
		b[len(b) - 3] = len(b) - 2
	if b[len(b) - 1] > b[len(b) - 2]:
		print('YES')
	else:
		print('NO')