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.*;
  
  public final class Main {
  
      static PrintWriter out = new PrintWriter(System.out);
      static FastReader in = new FastReader();
      static Pair[] moves = new Pair[]{new Pair(-1, 0), new Pair(0, 1), new Pair(1, 0), new Pair(0, -1)};
      static int mod = (int) (1e9 + 7);
      static int mod2 = 998244353;
  
      public static void main(String[] args) {
          int tt = i();
          while (tt-- > 0) {
              solve();
              //out.println(System.currentTimeMillis());
          }
          out.flush();
      }
  
      public static void solve() {
  
  //        int n = 100000;
  //        int[] a = new int[n];
  //        for (int i = 0; i < n; i++) {
  //            a[i]=i+1;
  //        }
  //        shuffle(a);
  //        out.println(System.currentTimeMillis());
          int n = i();
          int[] a = input(n);
          int[] loc = new int[n + 1];
          Arrays.fill(loc, -1);
          TreeSet<Integer> toMove = new TreeSet<>();
          for (int i = 0; i < n; i++) {
              if (loc[a[i]] > -1) {
                  out.println("YES");
                  return;
              } else {
                  loc[a[i]] = i;
                  if (a[i] != i + 1) {
                      toMove.add(a[i]);
                  }
              }
          }
  
          while (toMove.size() > 0) {
              if (toMove.size() <= 2) {
                  out.println("NO");
                  return;
              }
              boolean last = false;
              if (toMove.size() == 3) {
                  last = true;
              }
              int x = -1;
              for (int tm : toMove) {
                  x = tm;
                  break;
              }
              int z = a[x - 1];
              int y = -1;
              for (int tm : toMove) {
                  if (tm == x || tm == z) {
                      continue;
                  }
                  y = tm;
                  break;
              }
              int locx = loc[x];
              int locy = loc[y];
              int locz = loc[z];
              a[locz] = x;
              a[locy] = z;
              a[locx] = y;
              loc[x] = locz;
              loc[z] = locy;
              loc[y] = locx;
              if (locz + 1 == x) {
                  toMove.remove(x);
              }
              if (locy + 1 == z) {
                  toMove.remove(z);
              }
              if (locx + 1 == y) {
                  toMove.remove(y);
              }
  
              if (last && toMove.size() > 0) {
                  out.println("NO");
                  return;
              }
          }
  
          out.println("YES");
      }
  
      static long[] pre(int[] a) {
          long[] pre = new long[a.length + 1];
          pre[0] = 0;
          for (int i = 0; i < a.length; i++) {
              pre[i + 1] = pre[i] + a[i];
          }
          return pre;
      }
  
      static long[] pre(long[] a) {
          long[] pre = new long[a.length + 1];
          pre[0] = 0;
          for (int i = 0; i < a.length; i++) {
              pre[i + 1] = pre[i] + a[i];
          }
          return pre;
      }
  
      static void print(char A[]) {
          for (char c : A) {
              out.print(c);
          }
          out.println();
      }
  
      static void print(boolean A[]) {
          for (boolean c : A) {
              out.print(c + " ");
          }
          out.println();
      }
  
      static void print(int A[]) {
          for (int c : A) {
              out.print(c + " ");
          }
          out.println();
      }
  
      static void print(long A[]) {
          for (long i : A) {
              out.print(i + " ");
          }
          out.println();
      }
  
      static void print(List<Integer> A) {
          for (int a : A) {
              out.print(a + " ");
          }
      }
  
      static int i() {
          return in.nextInt();
      }
  
      static long l() {
          return in.nextLong();
      }
  
      static double d() {
          return in.nextDouble();
      }
  
      static String s() {
          return in.nextLine();
      }
  
      static String c() {
          return in.next();
      }
  
      static int[][] inputWithIdx(int N) {
          int A[][] = new int[N][2];
          for (int i = 0; i < N; i++) {
              A[i] = new int[]{i, in.nextInt()};
          }
          return A;
      }
  
      static int[] input(int N) {
          int A[] = new int[N];
          for (int i = 0; i < N; i++) {
              A[i] = in.nextInt();
          }
          return A;
      }
  
      static long[] inputLong(int N) {
          long A[] = new long[N];
          for (int i = 0; i < A.length; i++) {
              A[i] = in.nextLong();
          }
          return A;
      }
  
      static int GCD(int a, int b) {
          if (b == 0) {
              return a;
          } else {
              return GCD(b, a % b);
          }
      }
  
      static long GCD(long a, long b) {
          if (b == 0) {
              return a;
          } else {
              return GCD(b, a % b);
          }
      }
  
      static long LCM(int a, int b) {
          return (long) a / GCD(a, b) * b;
      }
  
      static long LCM(long a, long b) {
          return a / GCD(a, b) * b;
      }
  
      static void shuffle(int[] arr) {
          for (int i = 0; i < arr.length; i++) {
              int rand = (int) (Math.random() * arr.length);
              int temp = arr[rand];
              arr[rand] = arr[i];
              arr[i] = temp;
          }
      }
  
      static void shuffleAndSort(int[] arr) {
          for (int i = 0; i < arr.length; i++) {
              int rand = (int) (Math.random() * arr.length);
              int temp = arr[rand];
              arr[rand] = arr[i];
              arr[i] = temp;
          }
          Arrays.sort(arr);
      }
  
      static void shuffleAndSort(int[][] arr, Comparator<? super int[]> comparator) {
          for (int i = 0; i < arr.length; i++) {
              int rand = (int) (Math.random() * arr.length);
              int[] temp = arr[rand];
              arr[rand] = arr[i];
              arr[i] = temp;
          }
          Arrays.sort(arr, comparator);
      }
  
      static void shuffleAndSort(long[] arr) {
          for (int i = 0; i < arr.length; i++) {
              int rand = (int) (Math.random() * arr.length);
              long temp = arr[rand];
              arr[rand] = arr[i];
              arr[i] = temp;
          }
          Arrays.sort(arr);
      }
  
      static boolean isPerfectSquare(double number) {
          double sqrt = Math.sqrt(number);
          return ((sqrt - Math.floor(sqrt)) == 0);
      }
  
      static void swap(int A[], int a, int b) {
          int t = A[a];
          A[a] = A[b];
          A[b] = t;
      }
  
      static void swap(char A[], int a, int b) {
          char t = A[a];
          A[a] = A[b];
          A[b] = t;
      }
  
      static long pow(long a, long b, int mod) {
          long pow = 1;
          long x = a;
          while (b != 0) {
              if ((b & 1) != 0) {
                  pow = (pow * x) % mod;
              }
              x = (x * x) % mod;
              b /= 2;
          }
          return pow;
      }
  
      static long pow(long a, long b) {
          long pow = 1;
          long x = a;
          while (b != 0) {
              if ((b & 1) != 0) {
                  pow *= x;
              }
              x = x * x;
              b /= 2;
          }
          return pow;
      }
  
      static long modInverse(long x, int mod) {
          return pow(x, mod - 2, mod);
      }
  
      static boolean isPrime(long N) {
          if (N <= 1) {
              return false;
          }
          if (N <= 3) {
              return true;
          }
          if (N % 2 == 0 || N % 3 == 0) {
              return false;
          }
          for (int i = 5; i * i <= N; i = i + 6) {
              if (N % i == 0 || N % (i + 2) == 0) {
                  return false;
              }
          }
          return true;
      }
  
      public static String reverse(String str) {
          if (str == null) {
              return null;
          }
          return new StringBuilder(str).reverse().toString();
      }
  
      public static void reverse(int[] arr) {
          for (int i = 0; i < arr.length / 2; i++) {
              int tmp = arr[i];
              arr[arr.length - 1 - i] = tmp;
              arr[i] = arr[arr.length - 1 - i];
          }
      }
  
      public static String repeat(char ch, int repeat) {
          if (repeat <= 0) {
              return "";
          }
          final char[] buf = new char[repeat];
          for (int i = repeat - 1; i >= 0; i--) {
              buf[i] = ch;
          }
          return new String(buf);
      }
  
      public static int[] manacher(String s) {
          char[] chars = s.toCharArray();
          int n = s.length();
          int[] d1 = new int[n];
          for (int i = 0, l = 0, r = -1; i < n; i++) {
              int k = (i > r) ? 1 : Math.min(d1[l + r - i], r - i + 1);
              while (0 <= i - k && i + k < n && chars[i - k] == chars[i + k]) {
                  k++;
              }
              d1[i] = k--;
              if (i + k > r) {
                  l = i - k;
                  r = i + k;
              }
          }
          return d1;
      }
  
      public static int[] kmp(String s) {
          int n = s.length();
          int[] res = new int[n];
          for (int i = 1; i < n; ++i) {
              int j = res[i - 1];
              while (j > 0 && s.charAt(i) != s.charAt(j)) {
                  j = res[j - 1];
              }
              if (s.charAt(i) == s.charAt(j)) {
                  ++j;
              }
              res[i] = j;
          }
          return res;
      }
  }
  
  class Pair {
  
      int i;
      int j;
  
      Pair(int i, int j) {
          this.i = i;
          this.j = j;
      }
  
      @Override
      public boolean equals(Object o) {
          if (this == o) {
              return true;
          }
          if (o == null || getClass() != o.getClass()) {
              return false;
          }
          Pair pair = (Pair) o;
          return i == pair.i && j == pair.j;
      }
  
      @Override
      public int hashCode() {
          return Objects.hash(i, j);
      }
  }
  
  class FastReader {
  
      BufferedReader br;
      StringTokenizer st;
  
      public FastReader() {
          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;
      }
  }
  
  class Node {
  
      int val;
  
      public Node(int val) {
          this.val = val;
      }
  }
  
  
  class ST {
  
      int n;
      Node[] st;
  
      ST(int n) {
          this.n = n;
          st = new Node[4 * Integer.highestOneBit(n)];
      }
  
      void build(Node[] nodes) {
          build(0, 0, n - 1, nodes);
      }
  
      private void build(int id, int l, int r, Node[] nodes) {
          if (l == r) {
              st[id] = nodes[l];
              return;
          }
          int mid = (l + r) >> 1;
          build((id << 1) + 1, l, mid, nodes);
          build((id << 1) + 2, mid + 1, r, nodes);
          st[id] = comb(st[(id << 1) + 1], st[(id << 1) + 2]);
      }
  
      void update(int i, Node node) {
          update(0, 0, n - 1, i, node);
      }
  
      private void update(int id, int l, int r, int i, Node node) {
          if (i < l || r < i) {
              return;
          }
          if (l == r) {
              st[id] = node;
              return;
          }
          int mid = (l + r) >> 1;
          update((id << 1) + 1, l, mid, i, node);
          update((id << 1) + 2, mid + 1, r, i, node);
          st[id] = comb(st[(id << 1) + 1], st[(id << 1) + 2]);
      }
  
      Node get(int x, int y) {
          return get(0, 0, n - 1, x, y);
      }
  
      private Node get(int id, int l, int r, int x, int y) {
          if (x > r || y < l) {
              return new Node(0);
          }
          if (x <= l && r <= y) {
              return st[id];
          }
          int mid = (l + r) >> 1;
          return comb(get((id << 1) + 1, l, mid, x, y), get((id << 1) + 2, mid + 1, r, x, y));
      }
  
      Node comb(Node a, Node b) {
          if (a == null) {
              return b;
          }
          if (b == null) {
              return a;
          }
          return new Node(a.val | b.val);
      }
  }