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.*;
  import java.util.*;
  import java.lang.*;
  
  public class cp18{
      static class Reader {
          static BufferedReader reader;
          static StringTokenizer tokenizer;
  
          static void init(InputStream input) {
              reader = new BufferedReader(
                      new InputStreamReader(input));
              tokenizer = new StringTokenizer("");
          }
  
          static String next() throws IOException {
              while (!tokenizer.hasMoreTokens()) {
                  //TODO add check for eof if necessary
                  tokenizer = new StringTokenizer(
                          reader.readLine());
              }
              return tokenizer.nextToken();
          }
  
          static int nextInt() throws IOException {
              return Integer.parseInt(next());
          }
  
          static double nextDouble() throws IOException {
              return Double.parseDouble(next());
          }
  
          static long nextLong() throws IOException {
              return Long.parseLong(next());
          }
      }
  
      static class disjointSet{
          HashMap<Integer, Node> mp= new HashMap<>();
  
          public static class Node{
              int data;
              Node parent;
              int rank;
          }
          public void create(int val){
              Node nn= new Node();
              nn.data=val;
              nn.parent=nn;
              nn.rank=0;
              mp.put(val,nn);
          }
  
          public int findparent(int val){
  
              return findparentn(mp.get(val)).data;
  
          }
  
  
          public Node findparentn(Node n){
              if(n==n.parent){
                  return n;
              }
              Node rr= findparentn(n.parent);
              n.parent=rr;
              return rr;
          }
  
  
  
          public void union(int val1, int val2){                                                                               // can also be used to check cycles
  
              Node n1= findparentn(mp.get(val1));
              Node n2= findparentn(mp.get(val2));
  
  
              if(n1.data==n2.data) {
                  return;
              }
  
  
  
              if(n1.rank<n2.rank){
                  n1.parent=n2;
              }
  
              else if(n2.rank<n1.rank){
                  n2.parent=n1;
              }
  
              else {
                  n2.parent=n1;
                  n1.rank++;
              }
  
          }
      }
  
  
      public static void main(String[] args)  throws IOException {
          Reader.init(System.in);
          BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
          int t= Reader.nextInt();
          for (int tt = 0; tt <t ; tt++) {
  
           int n= Reader.nextInt();
           int arr[]= new int[n];
           Set<Integer>st= new HashSet<>();
           for (int i = 0; i <n ; i++) {
                  arr[i]= Reader.nextInt();
                  st.add(arr[i]);
           }
           if(st.size()<n){
               out.append("YES"+"\n");
           }
           else {
  
               disjointSet set = new disjointSet();
               for (int i = 1; i <= n; i++) {
                   set.create(i);
               }
  
               for (int i = 0; i < n; i++) {
                   set.union(arr[i], i + 1);
               }
  
               int sizes[]= new int[n+1];
  
               for (int i = 0; i <n ; i++) {
                   int x= set.findparent(arr[i]);
                   sizes[x]++;
               }
               int count=0;
               for (int i = 0; i <n+1 ; i++) {
                   if(sizes[i]>0 && sizes[i]%2==0){
                       count++;
                   }
               }
               if(count%2==0){
                   out.append("YES"+"\n");
               }
               else{
                   out.append("NO"+"\n");
               }
  
  
  
           }
  
  
  
          }
          out.flush();
          out.close();
      }
  
  
  }