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.*;
  import java.math.*;
  import java.lang.*;
  
  public class d {
      
      // static int mod = 998244353;
      static int mod = 1000000007;
  
      public static class Reader {
          final private int BUFFER_SIZE = 1 << 16;
          private DataInputStream din;
          private byte[] buffer;
          private int bufferPointer, bytesRead;
   
          public Reader()
          {
              din = new DataInputStream(System.in);
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
   
          public Reader(String file_name) throws IOException
          {
              din = new DataInputStream(
                  new FileInputStream(file_name));
              buffer = new byte[BUFFER_SIZE];
              bufferPointer = bytesRead = 0;
          }
   
          public String readLine() throws IOException
          {
              byte[] buf = new byte[64]; // line length
              int cnt = 0, c;
              while ((c = read()) != -1) {
                  if (c == '\n') {
                      if (cnt != 0) {
                          break;
                      }
                      else {
                          continue;
                      }
                  }
                  buf[cnt++] = (byte)c;
              }
              return new String(buf, 0, cnt);
          }
   
          public int nextInt() throws IOException
          {
              int ret = 0;
              byte c = read();
              while (c <= ' ') {
                  c = read();
              }
              boolean neg = (c == '-');
              if (neg)
                  c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
   
              if (neg)
                  return -ret;
              return ret;
          }
   
          public long nextLong() throws IOException
          {
              long ret = 0;
              byte c = read();
              while (c <= ' ')
                  c = read();
              boolean neg = (c == '-');
              if (neg)
                  c = read();
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
              if (neg)
                  return -ret;
              return ret;
          }
   
          public double nextDouble() throws IOException
          {
              double ret = 0, div = 1;
              byte c = read();
              while (c <= ' ')
                  c = read();
              boolean neg = (c == '-');
              if (neg)
                  c = read();
   
              do {
                  ret = ret * 10 + c - '0';
              } while ((c = read()) >= '0' && c <= '9');
   
              if (c == '.') {
                  while ((c = read()) >= '0' && c <= '9') {
                      ret += (c - '0') / (div *= 10);
                  }
              }
   
              if (neg)
                  return -ret;
              return ret;
          }
   
          private void fillBuffer() throws IOException
          {
              bytesRead = din.read(buffer, bufferPointer = 0,
                                   BUFFER_SIZE);
              if (bytesRead == -1)
                  buffer[0] = -1;
          }
   
          private byte read() throws IOException
          {
              if (bufferPointer == bytesRead)
                  fillBuffer();
              return buffer[bufferPointer++];
          }
   
          public void close() throws IOException
          {
              if (din == null)
                  return;
              din.close();
          }
      }
  
      public static void main(String[] args) throws Exception {
          Reader scn = new Reader();
          PrintWriter pw = new PrintWriter(System.out);
          int t = scn.nextInt();
          outer : while(t-->0){
              int n = scn.nextInt();
              int max = Integer.MIN_VALUE;
              int[] arr = new int[n+1];
              HashMap<Integer, Integer> hm = new HashMap<>();
              for(int i=1; i<=n; i++){
                  arr[i] = scn.nextInt();
                  max = Math.max(max, arr[i]);
                  hm.put(arr[i], hm.getOrDefault(arr[i], 0) + 1);
              }
              if(n == 1){
                  pw.println("YES");
                  continue outer;
              }
              if(n == 2){
                  if(arr[1] <= arr[2]){
                      pw.println("YES");
                      continue outer;
                  }else{
                      pw.println("NO");
                      continue outer;
                  }
              }
              if(n >= 3){
                  for(int key : hm.keySet()){
                      int val = hm.get(key);
                      if(val >= 2){
                          pw.println("YES");
                          continue outer;
                      }
                  }
                  long[] BIT = new long[max+1]; 
                  long ans = 0l;
                  for(int i=n; i>=1; i--){
                      update(BIT, arr[i], 1L, max);
                      ans += query(BIT, arr[i] - 1);
                  }
                  if(ans % 2 == 0){
                      pw.println("YES");
                      continue outer;
                  }else{
                      pw.println("NO");
                      continue outer;
                  }
              }
          }
          pw.close();
      }
  
      //TC-O(logn)
      private static void update(long[] BIT, int i, long increment, int n){
          while(i<=n){
              BIT[i] += increment;
              i += (i & (-i));
          }
      }
  
      // sum till ith query 
      //TC-O(logn)
      private static long query(long[] BIT, int i){
          long sum = 0L;
          while(i != 0){
              sum += BIT[i];
              i -= (i & (-i));
          }
          return sum;
      }
  
      public static class Pair{
          int x;
          int y;
  
          Pair(int x, int y){
              this.x = x;
              this.y = y;
          }
      }
  
      private static void sort(int[] arr) {
          List<Integer> list = new ArrayList<>();
          for (int i=0; i<arr.length; i++){
              list.add(arr[i]);
          }
          Collections.sort(list); // collections.sort uses nlogn in backend
          for (int i = 0; i < arr.length; i++){
              arr[i] = list.get(i);
          }
      }
  
      private static void sort(long[] arr) {
          List<Long> list = new ArrayList<>();
          for(int i=0; i<arr.length; i++){
              list.add(arr[i]);
          }
          Collections.sort(list); // collections.sort uses nlogn in backend
          for (int i = 0; i < arr.length; i++){
              arr[i] = list.get(i);
          }
      }
  
      // private static void sort(Pair[] arr) {
      //     List<Pair> list = new ArrayList<>();
      //     for(int i=0; i<arr.length; i++){
      //         list.add(arr[i]);
      //     }
      //     Collections.sort(list); // collections.sort uses nlogn in backend
      //     for (int i = 0; i < arr.length; i++){
      //         arr[i] = list.get(i);
      //     }
      // }
  
      private static void reverseSort(int[] arr){
          List<Integer> list = new ArrayList<>();
          for (int i=0; i<arr.length; i++){
              list.add(arr[i]);
          }
          Collections.sort(list, Collections.reverseOrder()); // collections.sort uses nlogn in backend
          for (int i = 0; i < arr.length; i++){
              arr[i] = list.get(i);
          }
      }
  
      private static void reverseSort(long[] arr){
          List<Long> list = new ArrayList<>();
          for (int i=0; i<arr.length; i++){
              list.add(arr[i]);
          }
          Collections.sort(list, Collections.reverseOrder()); // collections.sort uses nlogn in backend
          for (int i = 0; i < arr.length; i++){
              arr[i] = list.get(i);
          }
      }
  
      private static void reverseSort(ArrayList<Integer> list){
          Collections.sort(list, Collections.reverseOrder());
      }
  
      private static int lowerBound(int[] arr, int x){
          int n = arr.length, si = 0, ei = n - 1;
          while(si <= ei){
              int mid = si + (ei - si)/2;
              if(arr[mid] == x){
                  if(mid-1 >= 0 && arr[mid-1] == arr[mid]){
                      ei = mid-1;
                  }else{
                      return mid;
                  }
              }else if(arr[mid] > x){
                  ei = mid - 1; 
              }else{
                  si = mid+1;
              }
          }
          return si; 
      }
  
      private static int upperBound(int[] arr, int x){
          int n = arr.length, si = 0, ei = n - 1;
          while(si <= ei){
              int mid = si + (ei - si)/2;
              if(arr[mid] == x){
                  if(mid+1 < n && arr[mid+1] == arr[mid]){
                      si = mid+1;
                  }else{
                      return mid + 1;
                  }
              }else if(arr[mid] > x){
                  ei = mid - 1; 
              }else{
                  si = mid+1;
              }
          }
          return si; 
      }
  
      private static int upperBound(ArrayList<Integer> list, int x){
          int n = list.size(), si = 0, ei = n - 1;
          while(si <= ei){
              int mid = si + (ei - si)/2;
              if(list.get(mid) == x){
                  if(mid+1 < n && list.get(mid+1) == list.get(mid)){
                      si = mid+1;
                  }else{
                      return mid + 1;
                  }
              }else if(list.get(mid) > x){
                  ei = mid - 1; 
              }else{
                  si = mid+1;
              }
          }
          return si; 
      }
  
      // (x^y)%p in O(logy)
      private static long power(long x, long y){
          long res = 1; 
          x = x % mod;
          while(y > 0){
              if ((y & 1) == 1){
                  res = (res * x) % mod;
              }
              y = y >> 1; 
              x = (x * x) % mod;
          }
          return res;
      }
  
      public static boolean nextPermutation(int[] arr) {
          if(arr == null || arr.length <= 1){
              return false;
          }
          
          int last = arr.length-2;
          while(last >= 0){
              if(arr[last] < arr[last+1]){
                  break;
              }
              last--;
          }
  
          if (last < 0){
                return false;
          }
          
          if(last >= 0){
              int nextGreater = arr.length-1;
              for(int i=arr.length-1; i>last; i--){
                  if(arr[i] > arr[last]){
                      nextGreater = i;
                      break;
                  }
              }
              swap(arr, last, nextGreater);
          }
          
          reverse(arr, last+1, arr.length-1);
          return true;
      }
      
      private static void swap(int[] arr, int i, int j){
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
      
      private static void reverse(int[] arr, int i, int j){
          while(i < j){
              swap(arr, i++, j--);
          }
      }
  
      private static String reverseStr(String s){
          StringBuilder sb = new StringBuilder(s);
          return sb.reverse().toString();
      }
  
      // TC- O(logmax(a,b))
      private static int gcd(int a, int b) {
          if(a == 0){
              return b;
          }
          return gcd(b%a, a);
      }
  
      private static long gcd(long a, long b) {
          if(a == 0L){
              return b;
          }
          return gcd(b%a, a);
      }
  
      private static long lcm(long a, long b) {
          return a / gcd(a, b) * b;
      }
  
      // TC- O(logmax(a,b))
      private static int lcm(int a, int b) {
          return a / gcd(a, b) * b;
      }
  
      private static long inv(long x){
          return power(x, mod - 2);
      }
  
      private static long summation(long n){
          return (n * (n + 1L)) >> 1;
      } 
  }