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.io.PrintStream;
  import java.util.Arrays;
  import java.util.Comparator;
  import java.util.Scanner;
  
  public class D {
  
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          PrintStream out = System.out;
  
          int t = sc.nextInt();
          for (int i = 0; i < t; i++) {
              int n = sc.nextInt();
              int[] arr = new int[n];
              for (int j = 0; j < n; j++) {
                  arr[j] = sc.nextInt();
              }
              out.println(solve(arr));
          }
      }
  
      private static String solve(int[] arr) {
          Pair[] tmpArray = new Pair[arr.length];
          for (int i = 0; i < arr.length; i++) {
              tmpArray[i] = new Pair(arr[i], i);
          }
          Arrays.sort(tmpArray, Comparator.comparingInt(p -> p.a));
          int order = 0;
          for (int i = 0; i < tmpArray.length; i++) {
              if (i > 0 && tmpArray[i].a == tmpArray[i - 1].a) {
                  return "YES";
              }
              arr[tmpArray[i].b] = order++;
          }
  
          SegmentTree tree = new SegmentTree(arr.length);
  
          long trans = 0;
          for (int a : arr) {
              trans += tree.get(a);
              if (a > 0) {
                  tree.add(a - 1);
              }
          }
          return trans % 2 == 0 ? "YES" : "NO";
      }
  
      static class Pair {
          int a;
          int b;
  
          Pair(int a, int b) {
              this.a = a;
              this.b = b;
          }
  
          @Override
          public String toString() {
              return "Pair{" +
                      "a=" + a +
                      ", b=" + b +
                      '}';
          }
      }
  
      static class SegmentTree {
  
          long[] tree;
  
          SegmentTree(int size) {
              int pow = 1;
              while (pow < size) {
                  pow *= 2;
              }
              tree = new long[2 * pow - 1];
          }
  
          void add(int n) {
              add(0, 0, tree.length / 2, 0, n);
          }
  
          long get(int i) {
              int v = tree.length / 2 + i;
              long res = 0;
              while (v >= 0) {
                  res += tree[v];
                  v = (v - 1) / 2;
                  if (v == 0) {
                      break;
                  }
              }
              return res;
          }
  
          private void add(int v, int curL, int curR, int l, int r) {
              if (l > curR || r < curL) {
                  return;
              }
              if (curL >= l && curR <= r) {
                  tree[v] += 1;
                  return;
              }
              add(v * 2 + 1, curL, (curR + curL) / 2, l, r);
              add(v * 2 + 2, (curR + curL) / 2 + 1, curR, l, r);
          }
      }
  }
  