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 {
      public static void main(String[] args) throws FileNotFoundException{
          FastScanner fs = new FastScanner();
          PrintWriter out = new PrintWriter(System.out);
          int t = fs.nextInt();
          while(t > 0){
              int n = fs.nextInt();
              boolean seen[] = new boolean[n + 10];
              long freq[] = new long[n + 10];
              SegmentTree st = new SegmentTree(0, freq.length - 1, freq);
              long tot = 0;
              boolean ok = false;
              for(int i = 0; i < n; i++){
                  int elem = fs.nextInt();
                  if(seen[elem]){
                      ok = true;
                  }
                  seen[elem] = true;
                  long inv = st.sumRangeQuery(elem + 1, freq.length - 1);
                  tot += inv;
                  st.pointUpdate(elem, st.sumRangeQuery(elem, elem) + 1);
              }
              if(tot % 2 == 0 || ok){
                  out.println("YES");
              } else {
                  out.println("NO");
              }
              t--;
          }
          out.close();
      }
  }
  class SegmentTree {
    private SegmentTree lTree, rTree;
    private int lIdx, rIdx;
    private long max, sum;
    private long lazy;
  
    public SegmentTree(int l, int r, long arr[]){
      lIdx = l;
      rIdx = r;
      lazy = 0;
      if(l == r){
        max = arr[l];
        sum = arr[l];
      } else {
        lTree = new SegmentTree(l, (r + l)/2, arr);
        rTree = new SegmentTree((r + l)/2 + 1, r, arr);
        max = Math.max(lTree.getMax(), rTree.getMax());
        sum = lTree.getSum() + rTree.getSum();
      }
    }
  
    public long getMax(){
      return max;
    }
  
    public long getSum(){
      return sum;
    }
  
    public long maxRangeQuery(int l, int r){
      if(lazy > 0){
        max += lazy;
        //System.out.println("UPDATED MY MAX TO " + max + " " + lazy + " " + lIdx + " " + rIdx);
        if(lTree != null){
          lTree.lazyPush(lazy);
        }
        if(rTree != null){
          rTree.lazyPush(lazy);
        }
        lazy = 0;
      }
      if(l > rIdx || r < lIdx){
        return Long.MIN_VALUE;
      }
      if(l <= lIdx && r >= rIdx){
        //System.out.println("CAPTURED RANGE " + lIdx + " " + rIdx + " " + min);
        return max;
      }
      return Math.max(lTree.maxRangeQuery(l, r), rTree.maxRangeQuery(l, r));
    }
  
    public long sumRangeQuery(int l, int r){
      if(lazy > 0){
        sum = (lazy * (rIdx - lIdx + 1));
        if(lTree != null){
          lTree.lazyPush(lazy);
        }
        if(rTree != null){
          rTree.lazyPush(lazy);
        }
        lazy = 0;
      }
      if(l > rIdx || r < lIdx){
        return 0;
      }
      if(l <= lIdx && r >= rIdx){
        return sum;
      }
      return lTree.sumRangeQuery(l, r) + rTree.sumRangeQuery(l, r);
    }
  
    public void lazyPush(long val){
      lazy += val;
    }
  
    public void rangeUpdate(int l, int r, long inc){
      if(lazy > 0){
        max += lazy;
        if(lTree != null){
          lTree.lazyPush(lazy);
        }
        if(rTree != null){
          rTree.lazyPush(lazy);
        }
        lazy = 0;
      }
      if(l > rIdx || r < lIdx){
        return;
      }
      if(l <= lIdx && r >= rIdx){
        //System.out.println("updated on " + lIdx + " " + rIdx);
        sum += inc * (rIdx - lIdx + 1);
        max += inc;
        if(lTree != null){
          lTree.lazyPush(inc);
        }
        if(rTree != null){
          rTree.lazyPush(inc);
        }
      } else {
        lTree.rangeUpdate(l, r, inc);
        rTree.rangeUpdate(l, r, inc);
        max = Math.max(lTree.getMax(), rTree.getMax());
        sum = lTree.getSum() + rTree.getSum();
      }
    }
  
    public void pointUpdate(int pos, long elem){
      if(lIdx != rIdx){
        if(pos <= (rIdx + lIdx)/2){
          lTree.pointUpdate(pos, elem);
        } else {
          rTree.pointUpdate(pos, elem);
        }
        max = Math.max(lTree.getMax(), rTree.getMax());
        sum = lTree.getSum() + rTree.getSum();
      } else {
        max = elem;
        sum = elem;
      }
    }
  
  }
  
  //FastScanner fetched from: https://gist.github.com/codekansas/998da051fba0005111d43b0d11246478
  class FastScanner {
      BufferedReader br;
      StringTokenizer st;
      
      public FastScanner() throws FileNotFoundException {
          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());
      }
  }
  