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.BufferedWriter;
  import java.io.IOException;
  import java.io.InputStream;
  import java.io.OutputStreamWriter;
  import java.math.BigInteger;
  
  import java.math.BigDecimal;
  import java.math.MathContext;
  import java.math.RoundingMode;
  
  
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.Collections;
  import java.util.HashMap;
  import java.util.HashSet;
  import java.util.Locale;
  import java.util.Map.Entry;
  import java.util.PriorityQueue;
  import java.util.Random;
  import java.util.Scanner;
  import java.util.TreeSet;
  
  
  
  public final class CF_759_D2_D{
  
  	static boolean verb=true;
  	static void log(Object X){if (verb) System.err.println(X);}
  	static void log(Object[] X){if (verb) {for (Object U:X) System.err.print(U+" ");System.err.println("");}}
  	static void log(int[] X){if (verb) {for (int U:X) System.err.print(U+" ");System.err.println("");}}
  	static void log(int[] X,int L){if (verb) {for (int i=0;i<L;i++) System.err.print(X[i]+" ");System.err.println("");}}
  	static void log(long[] X){if (verb) {for (long U:X) System.err.print(U+" ");System.err.println("");}}
  
  	static void logWln(Object X){if (verb) System.err.print(X);}
  	static void info(Object o){	System.out.println(o);}
  	static void output(Object o){outputWln(""+o+"\n");	}
  	static void outputWln(Object o){try {out.write(""+ o);} catch (Exception e) {}}
  
  
  	// Global vars
  	static BufferedWriter out;
  	static InputReader reader;
  
  	static long powerMod(long b,long e,long m){
  		long x=1;
  		while (e>0) {
  			if (e%2==1)
  				x=(b*x)%m;
  			b=(b*b)%m;
  			e=e/2;
  		}
  		return x; 
  	}
  
  
  
  	static void test() {
  		log("testing");
  		Random r=new Random();
  		int NTESTS=1000000000;
  		int NMAX=100;
  		//int MMAX=10000;
  		int VMAX=100;
  
  		for( int t=0;t<NTESTS;t++) {
  
  
  		}
  		log("done");
  	}
  
  
  
  
  
  	static int sign(int x) {
  		if (x>0)
  			return 1;
  		if (x==0)
  			return 0;
  		return -1;
  	}
  
  
  
  	static class Segment implements Comparable<Segment>{
  		int a;
  		int b;
  
  		public int compareTo(Segment X) {
  			if (a!=X.a)
  				return a-X.a;
  			if (b!=X.b)
  				return b-X.b;
  			return 0;
  		}
  
  		public Segment(int a, int b) {
  			this.a = a;
  			this.b = b;
  		}
  
  
  
  	}
  
  
  
  	// REVERSE
  	static class Composite implements Comparable<Composite>{
  		int x;
  		int t;
  
  		public int compareTo(Composite X) {
  			if (x!=X.x)
  				return -(x-X.x);
  			return t-X.t;
  		}
  
  		public Composite(int x, int t) {
  			this.x = x;
  			this.t = t;
  		}
  
  
  	}
  	static class BIT {
  
  		int[] tree;
  		int N;
  
  		BIT(int N){
  			tree=new int[N+1];
  			this.N=N;
  		}
  
  		void add(int idx,int val){
  			idx++;
  			while (idx<=N){
  				tree[idx]+=val;
  				idx+=idx & (-idx);
  			}
  		}
  		int read(int idx){
  			idx++;
  			int sum=0;
  			while (idx>0){
  				sum+=tree[idx];
  				idx-=idx & (-idx);
  			}
  			return sum;
  		}
  
  	}
  
  
  
  	// reverse segment --> list of segments 
  
  	static int mod=998244353;
  
  
  	static long getValueRound(int[] x,int k) {
  		long ans=0;
  		
  		int n=x.length;
  		if (n==0)
  			return 0;
  		int i=n-1;
  		while (i>=0) {
  			ans+=2*x[i];
  			i-=k;
  		}
  		//log("getValueRound");
  		//log(x);
  		//log(ans);
  		return ans;
  	}
  
  	static long getValueSimple(int[] x,int k) {
  		long ans=0;
  		int n=x.length;
  		if (n==0)
  			return 0;
  		int i=n-1;
  		while (i>=0) {
  			ans+=2*x[i];
  			i-=k;
  		}
  		ans-=x[n-1];
  		//log("getValueSimple");
  		//log(x);
  		//log(ans);
  	
  		return ans;
  	}
  
  
  	static void process() throws Exception {
  
  
  
  		out = new BufferedWriter(new OutputStreamWriter(System.out));
  		reader=new InputReader(System.in);
  		Locale.setDefault(Locale.US);
  		//Scanner sc=new Scanner(System.in);
  		//sc.useLocale(Locale.US);
  
  
  		//test();
  
  		int T=reader.readInt();
  		for (int t=0;t<T;t++) {
  
  			int n=reader.readInt();
  			int[] a=new int[n];
  			int[] b=new int[n];
  			
  			for (int i=0;i<n;i++) {
  				a[i]=reader.readInt()-1;
  				b[i]=a[i];
  			}
  			Arrays.sort(b);
  			boolean found=false;
  			for (int i=1;i<n;i++) {
  				if (b[i]==b[i-1])
  					found=true;
  			}
  			String ans="YES";
  			if (!found) {
  				// every element is ingle
  				// we calculate number of inversions
  				BIT bit=new BIT(n);
  				long tot=0;
  				for (int i=0;i<n;i++) {
  					int higher=i-bit.read(a[i]);
  					tot+=higher;
  					bit.add(a[i],1);
  				}
  				//log("tot:"+tot);
  				if (tot%2==1)
  					ans="NO";
  			}
  			output(ans);
  		}
  
  		try {
  			out.close();
  		}
  		catch (Exception EX){}
  
  
  	}
  
  
  	public static void main(String[] args) throws Exception {
  		process();
  
  	}
  
  	static final class InputReader {
  		private final InputStream stream;
  		private final byte[] buf = new byte[1024];
  		private int curChar;
  		private int numChars;
  
  		public InputReader(InputStream stream) {
  			this.stream = stream;
  		}
  
  		private int read() throws IOException {
  			if (curChar >= numChars) {
  				curChar = 0;
  				numChars = stream.read(buf);
  				if (numChars <= 0) {
  					return -1;
  				}
  			}
  			return buf[curChar++];
  		}
  
  
  		public final String readString() throws IOException {
  			int c = read();
  			while (isSpaceChar(c)) {
  				c = read();
  			}
  			StringBuilder res=new StringBuilder();
  			do {
  				res.append((char)c);
  				c = read();
  			} while (!isSpaceChar(c));
  			return res.toString();
  		}
  
  		public final int readInt() throws IOException {
  			int c = read();
  			boolean neg=false;
  			while (isSpaceChar(c)) {
  				c = read();
  			}
  			char d=(char)c;
  			//log("d:"+d);
  			if (d=='-') {
  				neg=true;
  				c = read();
  			}
  			int res = 0;
  			do {
  				res *= 10;
  				res += c - '0';
  				c = read();
  			} while (!isSpaceChar(c));
  			//log("res:"+res);
  			if (neg)
  				return -res;
  			return res;
  
  		}
  
  		public final long readLong() throws IOException {
  			int c = read();
  			boolean neg=false;
  			while (isSpaceChar(c)) {
  				c = read();
  			}
  			char d=(char)c;
  			//log("d:"+d);
  			if (d=='-') {
  				neg=true;
  				c = read();
  			}
  			long res = 0;
  			do {
  				res *= 10;
  				res += c - '0';
  				c = read();
  			} while (!isSpaceChar(c));
  			//log("res:"+res);
  			if (neg)
  				return -res;
  			return res;
  
  		}
  
  
  
  
  		private boolean isSpaceChar(int c) {
  			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
  		}
  	}
  
  
  }
  
  
  