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 random
  from bisect import bisect_left as lb
  from bisect import bisect_right as rb
  from collections import deque
  #sys.setrecursionlimit(10**8)
  from queue import PriorityQueue as pq
  from math import gcd
  #import math
  input_ = lambda: sys.stdin.readline().strip("\r\n")
  ii = lambda : int(input_())
  il = lambda : list(map(int, input_().split()))
  ilf = lambda : list(map(float, input_().split()))
  lii = lambda : list(map(int, list(ip())))
  ip = lambda : input_()
  fi = lambda : float(input_())
  ap = lambda ab,bc,cd : ab[bc].append(cd)
  li = lambda : list(input_())
  pr = lambda x : print(x)
  prinT = lambda x : print(x)
  f = lambda : sys.stdout.flush()
  inv =lambda x:pow(x,mod-2,mod)
  dx = [0,0,1,-1]
  dy = [1,-1,0,0]
  mod = 10**9 + 7
  mod1 = 998244353
  
  def get (a) :
      if (parent[a] == a) :
          return a
      parent[a] = get(parent[a])
      return parent[a]
  
  def join(a,b) :
      a = get(a)
      b = get(b)
  
      if (a == b) :
          return
  
      if (rank[a] < rank[b]) :
          a,b = b,a
  
      parent[b] = a
      rank[a] += rank[b]
  
  
  for _ in range (ii()) :
      n = ii()
      a = il()
  
      b = sorted(a)
  
      if (a == b) :
          print("YES")
          continue
  
      if (n <= 2) :
          print("NO")
          continue
  
      d = {}
  
      for i in a :
          d[i] = d.get(i,0) + 1
  
      fl = 0
  
      for i in d :
          if (d[i] > 1) :
              fl = 1
              break
      if (fl) :
          print("YES")
          continue
  
      parent = [i for i in range (n+1)]
      rank = [1 for i in range (n+1)]
  
      for i in range (n) :
          join(a[i],b[i])
  
      e = 0
      o = 0
  
      for i in range (1,n+1) :
          if (parent[i] == i) :
              if (rank[i]%2)   :
                  o += 1
              else :
                  e += 1
  
      if (e%2 and e != 0) :
          print("NO")
      else :
          print("YES")
  
  
      
  