human
Can you solve the below in PYTHON3?
Petya has an array of integers a_1, a_2, …, 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 ≤ i, j, k ≤ n) and apply i → j → k → 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.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 5 ⋅ 10^5). Description of the test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 5 ⋅ 10^5) — the length of the array a.

The second line of each test case contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n).

It is guaranteed that the sum of n over all test cases does not exceed 5 ⋅ 10^5.

Output

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).

Example

Input

7
1
1
2
2 2
2
2 1
3
1 2 3
3
2 1 3
3
3 1 2
4
2 1 4 3

Output

YES
YES
NO
YES
NO
YES
YES

Note

In the 6-th test case Petya can use the 3-cycle 1 → 3 → 2 → 1 to sort the array.

In the 7-th test case Petya can apply 1 → 3 → 2 → 1 and make a = [1, 4, 2, 3]. Then he can apply 2 → 4 → 3 → 2 and finally sort the array.

Can you provide a Python code to determine if Petya can sort his array a, i?
assistant
#Here is Python code to determine if Petya can sort his array a, i.

class SegmentTree():
    def __init__(self,arr,combinerFunction,isCommutative=True): # isCommutative means f(a,b)==f(b,a)
        self.n=len(arr)
        def cmb(a,b):
            if a==None: return b
            if b==None: return a
            return combinerFunction(a,b)
        self.cmb=cmb
        self.sz=self.n if isCommutative else pow(2,((self.n-1).bit_length())) # non-commutative needs power of 2 size
        self.t=[None]*(2*self.sz) # use None as initial value
        for i in range(self.n): self.t[i+self.sz]=arr[i]
        for i in range(self.sz-1,0,-1): self.pull(i)
    def pull(self,p):
        self.t[p]=self.cmb(self.t[2*p],self.t[2*p+1])
    def update(self,idx,val): # set val at idx
        idx+=self.sz
        self.t[idx]=val
        idx//=2
        while idx>0:
            self.pull(idx)
            idx//=2
    def query(self,l,r): # aggregated value in [l,r] inclusive
        l+=self.sz; r+=self.sz+1
        a=b=None
        while l<r:
            if l%2==1: a=self.cmb(a,self.t[l]); l+=1
            if r%2==1: r-=1; b=self.cmb(self.t[r],b)
            l//=2; r//=2
        return self.cmb(a,b)
def getMaxSegTree(arr):
    return SegmentTree(arr,lambda a,b:max(a,b),True)
def getMinSegTree(arr):
    return SegmentTree(arr,lambda a,b:min(a,b),True)
def getSumSegTree(arr):
    return SegmentTree(arr,lambda a,b:a+b,True)

def main():
    
    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        a = readIntArr()
        if len(set(a)) < n: # at least 1 repeated element
            allans.append('YES')
        else:
            # coord-compress
            b = sorted(a)
            mapp = {x : i for i, x in enumerate(b)}
            for i in range(n):
                a[i] = mapp[a[i]]
            # count inversions
            seggy = getSumSegTree([0] * n)
            invCnts = 0
            for x in a:
                if x < n - 1:
                    invCnts += seggy.query(x + 1, n - 1)
                seggy.update(x, 1)
            
            # since a...