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 E_Gardener_and_Tree implements Runnable{
  
         public static void main(String[] args) throws Exception {
          new Thread(null, new E_Gardener_and_Tree(), "E_Gardener_and_Tree", 1<<28).start();
         }
      public void run(){
           WRITE YOUR CODE HERE!!!!
           JUST WRITE EVERYTHING HERE WHICH YOU WRITE IN MAIN!!!
         }
  
    }
  */
  /////**************************************************************************
  
  
  public class D_Yet_Another_Sorting_Problem{
      public static void main(String[] args) {
          FastScanner s= new FastScanner();
          //PrintWriter out=new PrintWriter(System.out);
          //end of program
          //out.println(answer);
          //out.close();
          StringBuilder res = new StringBuilder();
          int t=s.nextInt();
          int p=0;
          while(p<t){
          int n=s.nextInt();
          long array[]= new long[n];
          long nice[]= new long[n+4];
          ArrayList<Long> list = new ArrayList<Long>();
          for(int i=0;i<n;i++){
              array[i]=s.nextLong();
              nice[(int)array[i]]++;
              list.add(array[i]);
          }
          Collections.sort(list);
          if(n<3){
              int check=0;
              for(int i=0;i<n;i++){
                  long a=array[i];
                  long b=list.get(i);
                  if(a!=b){
                      check=1;
                      break;
                  }
              }
              if(check==0){
                  res.append("YES \n");
              }
              else{
                  res.append("NO \n");
              }
          }
          else{
            //  System.out.println("jj");
              int flag=0;
              for(int i=0;i<n+4;i++){
                 // System.out.println(nice[i]);
                  if(nice[i]>1){
                      flag=1;
                      
                  }
              }
              if(flag==1){
                 // System.out.println("jj");
                  res.append("YES \n");
              }
              else{
                 // System.out.println("jj");
                  long pos[]= new long[n+5];
                  for(int i=0;i<n;i++){
                      long num=array[i];
                      pos[(int)array[i]]=i;
                  }
                  for(int i=n-1;i>=2;i--){
                      long correct=list.get(i);
                      long num=array[i];
                      if(num==correct){
                         // System.out.println("jj");
                          continue;
                      }
                      long yo=pos[(int)correct];
                      long index=0;
                      if(yo==0){
                          index=1;
                      }
                      long pada=array[(int)index];
                      array[i]=correct;
                      array[(int)index]=num;
                      array[(int)yo]=pada;
                      pos[(int)correct]=i;
                      pos[(int)num]=index;
                      pos[(int)pada]=yo;
  
                  }
                  int flag2=0;
                  for(int i=0;i<n;i++){
                      long a=array[i];
                      long b=list.get(i);
                      if(a!=b){
                          flag2=1;
                          break;
                      }
                  }
                  if(flag2==0){
                      res.append("YES \n");
                  }
                  else{
                      res.append("NO \n");
                  }
              }
          }
          p++;
      }
      System.out.println(res);
      }
      static class FastScanner {
  		BufferedReader br;
  		StringTokenizer st;
   
  		public FastScanner(String s) {
  			try {
  				br = new BufferedReader(new FileReader(s));
  			} catch (FileNotFoundException e) {
  				// TODO Auto-generated catch block
  				e.printStackTrace();
  			}
  		}
   
  		public FastScanner() {
  			br = new BufferedReader(new InputStreamReader(System.in));
  		}
   
  		String nextToken() {
  			while (st == null || !st.hasMoreElements()) {
  				try {
  					st = new StringTokenizer(br.readLine());
  				} catch (IOException e) {
  					// TODO Auto-generated catch block
  					e.printStackTrace();
  				}
  			}
  			return st.nextToken();
  		}
   
  		int nextInt() {
  			return Integer.parseInt(nextToken());
  		}
   
  		long nextLong() {
  			return Long.parseLong(nextToken());
  		}
   
  		double nextDouble() {
  			return Double.parseDouble(nextToken());
  		}
  	}
  
  
      static long modpower(long x, long y, long p)
       {
        long res = 1; // Initialize result
     
        x = x % p; // Update x if it is more than or
        // equal to p
     
        if (x == 0)
          return 0; // In case x is divisible by p;
     
        while (y > 0)
        {
     
          // If y is odd, multiply x with result
          if ((y & 1) != 0)
            res = (res * x) % p;
     
          // y must be even now
          y = y >> 1; // y = y/2
          x = (x * x) % p;
        }
        return res;
      }
  
    
     // SIMPLE POWER FUNCTION=>
  
  
        static long power(long x, long y)
          {
              long res = 1;     // Initialize result
          
              while (y > 0)
              {
              
                  // If y is odd, multiply x with result
                  if ((y & 1) != 0)
                      res = res * x;
          
                  // y must be even now
                  y = y >> 1; // y = y/2
                  x = x * x;  // Change x to x^2
              }
              return res;
          }
  
  
  
  
  
  }