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: import java.util.*;
  import java.io.*;
  public class Main {
     // For fast input output
     static class FastReader {
         BufferedReader br;
         StringTokenizer st;
         public FastReader()
         { try {br = new BufferedReader(
         new FileReader("input.txt"));
         PrintStream out = new PrintStream(new FileOutputStream("output.txt"));
         System.setOut(out);}
         catch(Exception e) { br = new BufferedReader(new InputStreamReader(System.in));}
         }
         String next()
         {
         while (st == null || !st.hasMoreElements()) {
                     try {st = new StringTokenizer(br.readLine());}
                     catch (IOException e) {
                     e.printStackTrace();}
                 }
                 return st.nextToken();
         }
         int nextInt() { return Integer.parseInt(next()); }
         long nextLong() { return Long.parseLong(next()); }
         double nextDouble() {return Double.parseDouble(next()); }
         String nextLine()
         {
             String str = "";
             try {
             str = br.readLine();
             }
             catch (IOException e) {
                 e.printStackTrace();
             }
             return str;
         }
     }
      // end of fast i/o code
      public static void main(String[] args) {
          FastReader reader = new FastReader();
          StringBuilder sb = new StringBuilder("");
          
          int t = reader.nextInt();
          int ans = 0;
          while(t-->0){
              ans = 0;
              int n = reader.nextInt();
              int arr[] = new int[n];
              ArrayList<Pair> list = new ArrayList<>();
              for(int i=0; i<n; i++){
                  arr[i] = reader.nextInt();
                  list.add(new Pair(i, arr[i]));
              }
              Collections.sort(list, (o1, o2)->(o1.b-o2.b));
  
              int prev = list.get(0).b;
              boolean unique = true;
              for(int i=1; i<n; i++){
                  int current = list.get(i).b;
                  if(current==prev){
                      unique = false;
                      break;
                  }
                  prev = current;
              }
  
              if(!unique){
                  sb.append("YES\n");
                  continue;
              }
  
              for(int i=0; i<n; i++){
                  int pos = list.get(i).a;
                  arr[pos] = i;
              }
  
              // sb.append(Arrays.toString(arr)+"<->\n");
  
              int swaps = 0;
              for(int i=0; i<n; i++){
                  if(arr[i]==-1){
                      continue;
                  }
                  int temp = i;
                  do{
                      temp = arr[temp];
                      swaps++;
                  }while(temp!=i);
                  swaps--;
                  temp = i;
                  do{
                      int next = arr[temp];
                      arr[temp] = -1;
                      temp = next;
                  }while(temp!=i);
              }
  
              // sb.append(swaps+"<--\n");
  
              if(swaps%2==0){
                  sb.append("YES\n");
              }else{
                  sb.append("NO\n");
              }
          }
          System.out.println(sb);
      }
  
      static class Pair{
          int a, b;
          Pair(int x, int y){
              a = x;
              b = y;
          }
      }
  }