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: /*
  stream Butter!
  eggyHide eggyVengeance
  I need U
  xiao rerun when
   */
  import static java.lang.Math.*;
  import java.util.*;
  import java.io.*;
  import java.math.*;
  
  public class x1591A
  {
      public static void main(String hi[]) throws Exception
      {
          BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(infile.readLine());
          int T = Integer.parseInt(st.nextToken());
          StringBuilder sb = new StringBuilder();
          outer:while(T-->0)
          {
              st = new StringTokenizer(infile.readLine());
              int N = Integer.parseInt(st.nextToken());
              int[] arr = readArr(N, infile, st);
              for(int i=0; i < N; i++)
                  arr[i]--;
              boolean[] lol = new boolean[N];
              for(int x: arr)
                  lol[x] = true;
              for(boolean b: lol)
                  if(!b)
                  {
                      sb.append("YES\n");
                      continue outer;
                  }
              FenwickTree bit = new FenwickTree(N+2);
              long res = 0L;
              for(int x: arr)
              {
                  x++;
                  res += bit.find(x+1, N);
                  bit.add(x, 1);
              }
              if(res%2 == 0)
                  sb.append("YES\n");
              else
                  sb.append("NO\n");
          }
          System.out.print(sb);
      }
      public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
      {
          int[] arr = new int[N];
          st = new StringTokenizer(infile.readLine());
          for(int i=0; i < N; i++)
              arr[i] = Integer.parseInt(st.nextToken());
          return arr;
      }
  }
  class FenwickTree
  {
      //Binary Indexed Tree
      //1 indexed
      public int[] tree;
      public int size;
  
      public FenwickTree(int size)
      {
          this.size = size;
          tree = new int[size+5];
      }
      public void add(int i, int v)
      {
          while(i <= size)
          {
              tree[i] += v;
              i += i&-i;
          }
      }
      public int find(int i)
      {
          int res = 0;
          while(i >= 1)
          {
              res += tree[i];
              i -= i&-i;
          }
          return res;
      }
      public int find(int l, int r)
      {
          return find(r)-find(l-1);
      }
  }