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 static java.lang.Math.*;
  
  public class D{
  	
  	public static void main(String[] args) throws IOException{
  		// br = new BufferedReader(new FileReader(".in"));
  		// out = new PrintWriter(new FileWriter(".out"));
  		// new Thread(null, new (), "fisa balls", 1<<28).start();
  		
  		int t =readInt();
  		outer: while(t-->0) {
  			int n =readInt();
  			
  			TreeMap<Integer, Integer> tm = new TreeMap<Integer, Integer>();
  			
  			for (int i = 0; i < n; i++) {
  				int x = readInt()-1;
  				tm.put(x, i);
  			}
  			
  			if (tm.size() != n) {
  				out.println("YES");
  				continue outer;
  			}
  			
  			int v = 0;
  			int[] p = new int[n];// pos in the array
  			int[] perm = new int[n]; // actual damn permutation
  			
  			for (Map.Entry<Integer, Integer> e: tm.entrySet()) {
  				p[v++] = e.getValue();
  			}
  			for (int i = 0; i < n; i++) perm[p[i]] = i;
  			
  			if (n==1){
  				out.println("YES");
  				continue;
  			}
  			else if (n==2) {
  				out.println(p[1] > p[0] ? "YES":"NO");
  				continue;
  			}
  			
  			for (int i = 0; i < n-3; i++) {
  				int pos1 = p[i];
  				int pos2 = i;
  				int pos3 = i;
  				for (; pos3 < n; pos3++) {
  					if (pos3 != pos1 && pos3 != pos2) break;
  				}
  				
  				//System.out.println(pos1 + " " + pos2 + " " + pos3);
  				// shift forwards, move element I into position I
  			
  				int temp = perm[pos1];
  				perm[pos1] = perm[pos2];
  				perm[pos2] = perm[pos3];
  				perm[pos3] = temp;
  				temp = perm[pos1];
  				perm[pos1] = perm[pos2];
  				perm[pos2] = perm[pos3];
  				perm[pos3] = temp;
  				
  				p[perm[pos1]] = pos1;
  				p[perm[pos2]] = pos2;
  				p[perm[pos3]] = pos3;
  				
  			}
  			/*
  			for (int i = 0; i < n; i++) {
  				out.println( i + " | " + p[i]);
  			}
  			for (int i = 0; i < n; i++) {
  				out.print(perm[i] + " ");
  			}
  			out.println();
  			*/
  			// check all 6 combos of the last 3 elements
  			if (p[n-3] < p[n-2] && p[n-2] < p[n-1]) out.println("YES");
  			else if (p[n-3] < p[n-1] && p[n-1] < p[n-2]) out.println("NO");
  			else if (p[n-2] < p[n-1] && p[n-1] < p[n-3]) out.println("YES");
  			else if (p[n-2] < p[n-3] && p[n-3] < p[n-1]) out.println("NO");
  			else if (p[n-1] < p[n-3] && p[n-3] < p[n-2]) out.println("YES");
  			else out.println("NO");
  			
  		}
  		
  		out.close();
  	}
  	
  	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  	static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
  	static StringTokenizer st = new StringTokenizer("");
  	static String read() throws IOException{
  		while (!st.hasMoreElements()) st = new StringTokenizer(br.readLine());
  		return st.nextToken();
  	}
  	public static int readInt() throws IOException{return Integer.parseInt(read());}
  	public static long readLong() throws IOException{return Long.parseLong(read());}
  }