Sorting

from random import shuffle
from heapq import heappush, heappop
import sys
 
def brute(A):
	prev = {tuple(A): None}
	Q = [(0, tuple(A))]
	while Q:
		d, state = heappop(Q)
		lstate = list(state)
		if lstate == sorted(lstate):
			path = [state]
			while prev[path[-1]] is not None:
				path.append(prev[path[-1]])
 
			path.reverse()
			"""
			for s in path:
				print(s, file=sys.stderr)
			"""
 
			return 'YES', path
 
		for i in range(N):
			for j in range(i+2, N-1):
				B = list(lstate)
				B[i], B[i+1], B[j], B[j+1] = B[j], B[j+1], B[i], B[i+1]
				tB = tuple(B)
				if tB not in prev:
					prev[tB] = state
					heappush(Q, (d, tB))
	else:
		from itertools import permutations
		#for perm in permutations(range(len(A))):
		#	if not perm in prev:
		#		print(perm)
		return 'NO', []
 
 
def swap(A, i, j):
	A[i], A[i+1], A[j], A[j+1] = A[j], A[j+1], A[i], A[i+1]
 
def g(A):
	N = len(A)
	tree = [0] * N
	def update(pos, v):
		while pos < N:
			tree[pos] += v
			pos |= pos + 1
 
	def query(pos):
		res = 0
		while pos > 0:
			res += tree[pos-1]
			pos &= pos-1
		return res
 
	invs = 0
	for i, v in enumerate(A):
		invs += i - query(v)
		update(v, 1)
 
	return 'YES' if invs % 2 == 0 else 'NO'
 
 
def f(A):
	for i in range(N):
		if A[i] == i: continue
		j = A.index(i)
		if j == N-1:
			if N - i <= 4:
				return 'NO', A
 
			swap(A, N-4, N-2)
			swap(A, i, N-3)
 
		elif j == i+1:
			if N - i <= 4:
				return 'NO', A
 
			swap(A, i+1, i+3)
			swap(A, i, i+3)
		else:
			swap(A, i, j)
	else:
		return 'YES', None
 
 
"""
N = 8
for _ in range(1000):
	A = list(range(N))
	shuffle(A)
	a1, path = brute(A)
	#break
	a2 = g(list(A))
	#a2, fail = f(list(A))
 
	if a1 == 'NO':
		print(a1, A)
 
	if a1 != a2:
		print(a1, a2, A)
		print(*path, sep='\n')
		break
 
raise SystemExit
"""
 
 
for _ in range(int(input())):
	N = int(input())
	A = list(map(lambda s: int(s)-1, input().split()))
 
	if N <= 4:
		a, _ = brute(A)
	else:
		a = g(A)
 
	print(a)

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED