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 D {
      static PrintWriter pw;
      
      void solve(int n, int[] a) {
          Set<Integer> as = new HashSet<>();
          for (int x : a) as.add(x);
          boolean res = reversePair(a) % 2 == 0 || as.size() != n;
          pr(res ? "YES" : "NO");
      }
  
      long reversePair(int[] a) {
          // tr(a);
          int n = a.length;
          int[] b = Arrays.copyOf(a, n);
          b = removeArrayDuplicates(b);
          Arrays.sort(b);
          Fenwick ft = new Fenwick(b.length);
          // tr(b);
          long res = 0;
          for (int i = 0; i < n; i++) {
              int idx = lower_bound2(b, a[i]);
              long query = ft.query(idx);
              // tr("idx", idx, "res", res, "query", query);
              res += i - query;
              ft.update(idx, 1);
          }
          return res;
      }
  
      int[] removeArrayDuplicates(int[] a) {
          Set<Integer> se = new HashSet<>();
          // tr("before", a);
          for (int x : a) se.add(x);
          // tr("set", se); // different order
          int n = se.size();
          int[] res = new int[n];
          int i = 0;
          for (int x : se) {
              res[i] = x;
              i++;
          }
          // tr("after", res);
          return res;
      }
  
      int lower_bound2(int[] a, int x) {
          int idx = Arrays.binarySearch(a, x);
          if (idx < 0) {
              return -idx - 1;
          }
          return idx;
      }
  
      class Fenwick {
          int n;
          int[] tree;
  
          Fenwick(int n) {
              this.n = n;
              this.tree = new int[n];
          }
  
          long query(int i) {
              i = Math.min(i + 1, n);
              // tr("tree", tree, "start", i);
              long sum = 0;
              while (i > 0) {
                  sum += this.tree[i - 1];
                  i -= i & -i;
              }
              return sum;
          }
  
          void update(int i, int v) {
              assert i >= 0 && i < n;
              i++;
              while (i <= n) {
                  this.tree[i - 1] += v;
                  i += i & -i;
              }
          }
      }
  
      private void run() {
          // read_write_file(); // comment this before submission
          FastScanner fs = new FastScanner();
          int t = fs.nextInt();
          while (t-- > 0) {
              int n = fs.nextInt();
              int[] a = fs.readArray(n);
              solve(n, a);
          }
      }
  
      private final String INPUT = "input.txt";
      private final String OUTPUT = "output.txt";
  
      void read_write_file() {
          FileInputStream instream = null;
          PrintStream outstream = null;
          try {
              instream = new FileInputStream(INPUT);
              outstream = new PrintStream(new FileOutputStream(OUTPUT));
              System.setIn(instream);
              System.setOut(outstream);
          } catch (Exception e) {
          }
      }
  
      public static void main(String[] args) {
          pw = new PrintWriter(System.out);
          new D().run();
          pw.close();
      }
  
      void pr(int num) {
          pw.println(num);
      }
  
      void pr(long num) {
          pw.println(num);
      }
  
      void pr(double num) {
          pw.println(num);
      }
  
      void pr(String s) {
          pw.println(s);
      }
  
      void pr(char c) {
          pw.println(c);
      }
  
      class FastScanner {
          BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer("");
  
          String next() {
              while (!st.hasMoreTokens())
                  try {
                      st = new StringTokenizer(br.readLine());
                  } catch (IOException e) {
                      e.printStackTrace();
                  }
              return st.nextToken();
          }
  
          int nextInt() {
              return Integer.parseInt(next());
          }
  
          int[] readArray(int n) {
              int[] a = new int[n];
              for (int i = 0; i < n; i++) a[i] = nextInt();
              return a;
          }
  
          long nextLong() {
              return Long.parseLong(next());
          }
  
          double nextDouble() {
              return Double.parseDouble(next());
          }
      }
  
      void tr(Object... o) {
          pw.println(Arrays.deepToString(o));
      }
  }