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.*;
  public class Main {
      public static void main(String args[])
      {
          FastReader input=new FastReader();
          PrintWriter out=new PrintWriter(System.out);
          int T=input.nextInt();
          while(T-->0)
          {
              int n=input.nextInt();
              int a[]=new int[n];
              HashSet<Integer> set=new HashSet<>();
              for(int i=0;i<n;i++)
              {
                  a[i]=input.nextInt();
                  set.add(a[i]);
              }
              int f=0;
              for(int i=1;i<n;i++)
              {
                  if(a[i]<a[i-1])
                  {
                      f=1;
                      break;
                  }
              }
              if(f==0)
              {
                  out.println("YES");
              }
              else
              {
                  if(set.size()<n)
                  {
                      out.println("YES");
                  }
                  else
                  {
                      ArrayList<Integer> list=new ArrayList<>();
                      int arr[]=new int[n+1];
                      for(int i=0;i<n;i++)
                      {
                          list.add(a[i]);
                          arr[a[i]]=i;
                      }
                      if(list.size()<3)
                      {
                          out.println("NO");
                      }
                      else
                      {
                          ArrayList<Integer> list1=new ArrayList<>(list);
                          Collections.sort(list1);
                          for(int i=0;i<list1.size()-2;i++)
                          {
                              int p=arr[list1.get(i)];
                              if(p!=i)
                              {
                                  int p1=i;
                                  int p2=0,p3=0;
                                  if(p==list.size()-1)
                                  {
                                      p2=p1+1;
                                      p3=p;
                                  }
                                  else
                                  {
                                      p2=p;
                                      p3=list.size()-1;
                                  }
                                  int shift=0;
                                  if(p==p2) shift=2;
                                  else shift=1;
                                  for(int j=0;j<shift;j++)
                                  {
                                      shift(arr,list,p1,p2,p3);
                                  }
                              }
                          }
                          int flag=0;
                          for(int i=1;i<list.size();i++)
                          {
                              if(list.get(i)<list.get(i-1))
                              {
                                  flag=1;
                                  break;
                              }
                          }
                          if(flag==1)
                          {
                              out.println("NO");
                          }
                          else
                          {
                              out.println("YES");
                          }
                      }
                  }
              }
          }
          out.close();
      }
      public static void shift(int arr[],ArrayList<Integer> list,int p1,int p2,int p3)
      {
          swap(p1,p2,list,arr);
          swap(p1,p3,list,arr);
      }
      public static void swap(int p1,int p2,ArrayList<Integer> list,int arr[])
      {
          int t=list.get(p1);
          list.set(p1,list.get(p2));
          list.set(p2,t);
          arr[list.get(p1)]=p1;
          arr[list.get(p2)]=p2;
      }
      static class FastReader
      {
          BufferedReader br;
          StringTokenizer st;
          public FastReader()
          {
              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());
          }
          double nextDouble()
          {
              return Double.parseDouble(next());
          }
          String nextLine()
          {
              String str="";
              try
              {
                  str=br.readLine();
              }
              catch (IOException e)
              {
                  e.printStackTrace();
              }
              return str;
          }
      }
  }