Yet Another Sorting Problem
Petya has an array of integers $$$a_1, a_2, \ldots, a_n$$$. He only likes sorted arrays. Unfortunately, the given array could be arbitrary, so Petya wants to sort it.Petya likes to challenge himself, so he wants to sort array using only $$$3$$$-cycles. More formally, in one operation he can pick $$$3$$$ pairwise distinct indices $$$i$$$, $$$j$$$, and $$$k$$$ ($$$1 \leq i, j, k \leq n$$$) and apply $$$i \to j \to k \to i$$$ cycle to the array $$$a$$$. It simultaneously places $$$a_i$$$ on position $$$j$$$, $$$a_j$$$ on position $$$k$$$, and $$$a_k$$$ on position $$$i$$$, without changing any other element.For example, if $$$a$$$ is $$$[10, 50, 20, 30, 40, 60]$$$ and he chooses $$$i = 2$$$, $$$j = 1$$$, $$$k = 5$$$, then the array becomes $$$[\underline{50}, \underline{40}, 20, 30, \underline{10}, 60]$$$.Petya can apply arbitrary number of $$$3$$$-cycles (possibly, zero). You are to determine if Petya can sort his array $$$a$$$, i. e. make it non-decreasing.
In the $$$6$$$-th test case Petya can use the $$$3$$$-cycle $$$1 \to 3 \to 2 \to 1$$$ to sort the array.In the $$$7$$$-th test case Petya can apply $$$1 \to 3 \to 2 \to 1$$$ and make $$$a = [1, 4, 2, 3]$$$. Then he can apply $$$2 \to 4 \to 3 \to 2$$$ and finally sort the array.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 5 \cdot 10^5$$$). Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
For each test case, print "YES" (without quotes) if Petya can sort the array $$$a$$$ using $$$3$$$-cycles, and "NO" (without quotes) otherwise. You can print each letter in any case (upper or lower).
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math, random
Z = stdin.readline

def inp(force_list=False):
    re = list(map(int, Z().split()))
    if len(re) == 1 and (not force_list):
        return re[0]
    return re

def inst():
    return Z().strip()

def gcd(x, y):
    while y:
        (x, y) = (y, x % y)
    return x
mod = 1000000007

class RMQ(object):

    def __init__(self, da, func):
        self.func = func
        n = len(da)
        sp = [[0 for i in range(25)] for i in range(n)]
        for i in range(n):
            sp[i][0] = da[i]
        for i in range(1, 25):
            for j in range(n):
                if j + (1 << i) >= n:
                    break
                sp[j][i] = func(sp[j][i - 1], sp[j + (1 << i)][i - 1])
        self.sp = sp
        self.log = [0] * (n + 1)
        for i in range(2, n + 1):
            self.log[i] = self.log[i // 2] + 1
        print(self.log)

    def query(self, l, r):
        j = self.log[r - l + 1]
        return self.func(self.sp[l][j], self.sp[r - (1 << j)][j])

def my_main():
    kase = inp()
    pans = []
    for _ in range(kase):
        n = inp()
        da = inp(True)
        if len(set(da)) != len(da):
            pans.append('YES')
            continue
        cycle = 0
        vi = [0] * n
        for i in range(n):
            if vi[i]:
                continue
            vi[i] = 1
            i = da[i] - 1
            while vi[i] == 0:
                vi[i] = 1
                i = da[i] - 1
                cycle += 1
        pans.append('YES' if cycle % 2 == 0 else 'NO')
    print('\n'.join(pans))
my_main()
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    if len(set(a)) < n:
        print('YES')
        continue
    swaps = 0
    for i in range(n):
        while a[i] != i + 1:
            (j, k) = (i, a[i] - 1)
            (a[j], a[k]) = (a[k], a[j])
            swaps += 1
    if swaps % 2 == 0:
        print('YES')
    else:
        print('NO')
for _ in range(int(input())):
    (n, a) = (int(input()), list(map(int, input().split())))
    if len(set(a)) < n:
        print('YES')
        continue
    sorted_a = sorted(a)
    num2i = {num: i for (i, num) in enumerate(sorted_a)}
    vis = [0] * n
    ans = 0
    for i in range(n):
        if vis[i]:
            continue
        (size, cur) = (0, i)
        while not vis[cur]:
            vis[cur] = 1
            (size, cur) = (size + 1, num2i[a[cur]])
        ans += size % 2 == 0
    print('YES') if ans == 0 or ans % 2 == 0 else print('NO')