description: 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.
solution: # cook your dish here
  import sys
  import bisect
  from bisect import bisect_left as lb
  from bisect import bisect_right as rb
  input_=lambda: sys.stdin.readline().strip("\r\n")
  from math import log
  from math import gcd
  from math import atan2,acos
  from random import randint
  sa=lambda :input_()
  sb=lambda:int(input_())
  sc=lambda:input_().split()
  sd=lambda:list(map(int,input_().split()))
  sflo=lambda:list(map(float,input_().split()))
  se=lambda:float(input_())
  sf=lambda:list(input_())
  flsh=lambda: sys.stdout.flush()
  sys.setrecursionlimit(3*10**5)
  mod=10**9+7
  mod1=998244353
  gp=[]
  cost=[]
  dp=[]
  mx=[]
  ans1=[]
  ans2=[]
  special=[]
  specnode=[]
  a=0
  kthpar=[]
  def dfs2(root,par):
      if par!=-1:
          dp[root]=dp[par]+1
      for i in range(1,20):
          if kthpar[root][i-1]!=-1:
              kthpar[root][i]=kthpar[kthpar[root][i-1]][i-1]
      for child in gp[root]:
          if child==par:continue
          kthpar[child][0]=root
          dfs(child,root)
          
  ans=0
  a=[]
  n,k=0,0
  b=[]
  vis=[]
  tot=0
  time=[]
  time1=[]
  adj=[]
  mx=-1
  eps=0.0000001
  x=0
  pref=[]
  lvl=[]
  gp=[]
  ans=[]
  f=0
  w=[]
  #Fenwick Tree point update range sum
  def update_it(bit,i,val):
      n=len(bit)
      while(i<n):
          bit[i]+=val
          i+=i&(-i)
  def get_ans(bit,i):
      n=len(bit)
      tot=0
      while(i>0):
          tot+=bit[i]
          i-=i&(-i)
      return tot
  class Disjoint_SU:
      def __init__(self,n):
          self.parent=[i for i in range(n)]
          self.size=[1 for i in range(n)]
      #find
      def lake_de(self,a):
          if a==self.parent[a]:
              return a
          self.parent[a]=self.lake_de(self.parent[a])
          return self.parent[a]
      #union
      #by size
      def jod(self,a,b):
          x=self.lake_de(a)
          y=self.lake_de(b)
          #for cycle in graph
          if x==y:
              return True
          if self.size[x]>self.size[y]:
              self.size[x]+=self.size[y]
              self.parent[y]=x
          else:
              self.size[y]+=self.size[x]
              self.parent[x]=y
          return False
  
  def dfs(i,prod,rem,n):
      if rem==0:
          while(i<len(n)):
              prod*=int(n[i])
              i+=1
          return prod
      if i==len(n):
          return prod
      mx=0
      for j in range(9-int(n[i])):
          mx=max(dfs(i+1,(int(n[i])+min(j,rem))*prod,rem-min(j,rem),n),mx)
      return mx
  def hnbhai(tc):
      n=sb()
      d={}
      a=sd()
      mx=0
      for i in a:
          d[i]=d.get(i,0)+1
          mx=max(d[i],mx)
      if mx>=2:
          print("YES")
          return
      if a==sorted(a):
          print("YES")
          return
      d=Disjoint_SU(n+1)
      b=sorted(a)
      for i in range(n):
          if a[i]!=b[i]:
              d.jod(a[i],b[i])
      od=0
      for i in range(1,n+1):
          if d.parent[i]==i:
              if d.size[i]%2==0:od+=1
      if od%2:
          print("NO")
          return
      print("YES")
  for _ in range(sb()):
      hnbhai(_+1)
  ##case
  
  #.
  