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: /**
   * check out my youtube channel sh0rkyboy
   * https://tinyurl.com/zdxe2y4z
   * I do screencasts, solutions, and other fun stuff in the future
   */
  
  import java.util.*;
  import java.io.*;
  import static java.lang.Math.min;
  import static java.lang.Math.abs;
  import static java.lang.Math.max;
  public class EdE {
  	static long[] mods = {1000000007, 998244353, 1000000009};
  	static long mod = mods[0];
  	public static MyScanner sc;
      public static PrintWriter out;
  	public static void main(String[] largewang) throws Exception{
  		// TODO Auto-generated method stub
   		sc = new MyScanner();
   		out = new PrintWriter(System.out);
   		int t = sc.nextInt();
   		while (t-->0) {
   			int n = sc.nextInt();
   			int[] arr = readArrayInt1(n);
   			Set<Integer> add = new HashSet<>();
   			for(int j : arr) {
   				add.add(j);
   			}
   			if (add.size() != n+1) {
   				out.println("YES");
   			} else {
   				int[] pos = new int[n+1];
   				for(int j = 1;j<=n;j++){
   					pos[arr[j]] = j;
   				}
   				int swap = 0;
   				for(int j = 1; j<=n;j++){
   					if (arr[j] != j) {
   						int temp = arr[j];
   						int next = j;
   						arr[pos[j]] = temp;
   						arr[j] = next;
   						pos[temp] = pos[j];
   						pos[next] = j;
   						swap++;
   					}
   				}
   				if (swap%2 == 0){
   					out.println("YES");
   				} else{
   					out.println("NO");
   				}
   			}
   		}
   		out.close();
   		
   	}
  	
  	public static void sort(int[] array){
  		ArrayList<Integer> copy = new ArrayList<>();
  		for (int i : array)
  			copy.add(i);
  		Collections.sort(copy);
  		for(int i = 0;i<array.length;i++)
  			array[i] = copy.get(i);
  	}
  	static String[] readArrayString(int n){
  		String[] array = new String[n];
  		for(int j =0 ;j<n;j++)
  			array[j] = sc.next();
  		return array;
  	}
  	static int[] readArrayInt(int n){
      	int[] array = new int[n];
      	for(int j = 0;j<n;j++)
      		array[j] = sc.nextInt();
      	return array;
      }
  	static int[] readArrayInt1(int n){
  		int[] array = new int[n+1];
  		for(int j = 1;j<=n;j++){
  			array[j] = sc.nextInt();
  		}
  		return array;
  	}
  	static long[] readArrayLong(int n){
  		long[] array = new long[n];
  		for(int j =0 ;j<n;j++)
  			array[j] = sc.nextLong();
  		return array;
  	}
  	static double[] readArrayDouble(int n){
  		double[] array = new double[n];
  		for(int j =0 ;j<n;j++)
  			array[j] = sc.nextDouble();
  		return array;
  	}
  	static int minIndex(int[] array){
  		int minValue = Integer.MAX_VALUE;
  		int minIndex = -1;
  		for(int j = 0;j<array.length;j++){
  			if (array[j] < minValue){
  				minValue = array[j];
  				minIndex = j;
  			}
  		}
  		return minIndex;
  	}
  	static int minIndex(long[] array){
  		long minValue = Long.MAX_VALUE;
  		int minIndex = -1;
  		for(int j = 0;j<array.length;j++){
  			if (array[j] < minValue){
  				minValue = array[j];
  				minIndex = j;
  			}
  		}
  		return minIndex;
  	}
  	static int minIndex(double[] array){
  		double minValue = Double.MAX_VALUE;
  		int minIndex = -1;
  		for(int j = 0;j<array.length;j++){
  			if (array[j] < minValue){
  				minValue = array[j];
  				minIndex = j;
  			}
  		}
  		return minIndex;
  	}
  	public static int power(long x, long y, long mod){
  		long ans = 1;
  		while(y>0){
  			if (y%2==1)
  				ans = (ans*x)%mod;
  			x = (x*x)%mod;
  			y/=2;
  		}
  		return (int)(ans);
  	}
  	static void verdict(boolean a){
          out.println(a ? "YES" : "NO");
      }
      public static class MyScanner {
          BufferedReader br;
          StringTokenizer st;
          public MyScanner() {
              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;
          }
          
      }	
  }
  
  //StringJoiner sj = new StringJoiner(" "); 
  //sj.add(strings)
  //sj.toString() gives string of those stuff w spaces or whatever that sequence is