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: #include <bits/stdc++.h>
  #pragma comment(linker, "/STACK:36777216")
  using namespace std;
  template <class T>
  inline T &RD(T &);
  template <class T>
  inline void OT(const T &);
  inline long long RD() {
    long long x;
    return RD(x);
  }
  inline double &RF(double &);
  inline double RF() {
    double x;
    return RF(x);
  }
  inline char *RS(char *s);
  inline char &RC(char &c);
  inline char RC();
  inline char &RC(char &c) {
    scanf(" %c", &c);
    return c;
  }
  inline char RC() {
    char c;
    return RC(c);
  }
  template <class T>
  inline T &RDD(T &);
  inline long long RDD() {
    long long x;
    return RDD(x);
  }
  template <class T0, class T1>
  inline T0 &RD(T0 &x0, T1 &x1) {
    RD(x0), RD(x1);
    return x0;
  }
  template <class T0, class T1, class T2>
  inline T0 &RD(T0 &x0, T1 &x1, T2 &x2) {
    RD(x0), RD(x1), RD(x2);
    return x0;
  }
  template <class T0, class T1, class T2, class T3>
  inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) {
    RD(x0), RD(x1), RD(x2), RD(x3);
    return x0;
  }
  template <class T0, class T1, class T2, class T3, class T4>
  inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) {
    RD(x0), RD(x1), RD(x2), RD(x3), RD(x4);
    return x0;
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5>
  inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) {
    RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5);
    return x0;
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
  inline T0 &RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) {
    RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6);
    return x0;
  }
  template <class T0, class T1>
  inline void OT(const T0 &x0, const T1 &x1) {
    OT(x0), OT(x1);
  }
  template <class T0, class T1, class T2>
  inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) {
    OT(x0), OT(x1), OT(x2);
  }
  template <class T0, class T1, class T2, class T3>
  inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) {
    OT(x0), OT(x1), OT(x2), OT(x3);
  }
  template <class T0, class T1, class T2, class T3, class T4>
  inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
                 const T4 &x4) {
    OT(x0), OT(x1), OT(x2), OT(x3), OT(x4);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5>
  inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
                 const T4 &x4, const T5 &x5) {
    OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
  inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3,
                 const T4 &x4, const T5 &x5, const T6 &x6) {
    OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6);
  }
  inline char &RC(char &a, char &b) {
    RC(a), RC(b);
    return a;
  }
  inline char &RC(char &a, char &b, char &c) {
    RC(a), RC(b), RC(c);
    return a;
  }
  inline char &RC(char &a, char &b, char &c, char &d) {
    RC(a), RC(b), RC(c), RC(d);
    return a;
  }
  inline char &RC(char &a, char &b, char &c, char &d, char &e) {
    RC(a), RC(b), RC(c), RC(d), RC(e);
    return a;
  }
  inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f) {
    RC(a), RC(b), RC(c), RC(d), RC(e), RC(f);
    return a;
  }
  inline char &RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) {
    RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g);
    return a;
  }
  inline double &RF(double &a, double &b) {
    RF(a), RF(b);
    return a;
  }
  inline double &RF(double &a, double &b, double &c) {
    RF(a), RF(b), RF(c);
    return a;
  }
  inline double &RF(double &a, double &b, double &c, double &d) {
    RF(a), RF(b), RF(c), RF(d);
    return a;
  }
  inline double &RF(double &a, double &b, double &c, double &d, double &e) {
    RF(a), RF(b), RF(c), RF(d), RF(e);
    return a;
  }
  inline double &RF(double &a, double &b, double &c, double &d, double &e,
                    double &f) {
    RF(a), RF(b), RF(c), RF(d), RF(e), RF(f);
    return a;
  }
  inline double &RF(double &a, double &b, double &c, double &d, double &e,
                    double &f, double &g) {
    RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g);
    return a;
  }
  inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
  inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
  template <class T0, class T1>
  inline T0 &RDD(T0 &a, T1 &b) {
    RDD(a), RDD(b);
    return a;
  }
  template <class T0, class T1, class T2>
  inline T1 &RDD(T0 &a, T1 &b, T2 &c) {
    RDD(a), RDD(b), RDD(c);
    return a;
  }
  template <class T>
  inline void RST(T &A) {
    memset(A, 0, sizeof(A));
  }
  template <class T>
  inline void FLC(T &A, int x) {
    memset(A, x, sizeof(A));
  }
  template <class T>
  inline void CLR(T &A) {
    A.clear();
  }
  template <class T0, class T1>
  inline void RST(T0 &A0, T1 &A1) {
    RST(A0), RST(A1);
  }
  template <class T0, class T1, class T2>
  inline void RST(T0 &A0, T1 &A1, T2 &A2) {
    RST(A0), RST(A1), RST(A2);
  }
  template <class T0, class T1, class T2, class T3>
  inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
    RST(A0), RST(A1), RST(A2), RST(A3);
  }
  template <class T0, class T1, class T2, class T3, class T4>
  inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
    RST(A0), RST(A1), RST(A2), RST(A3), RST(A4);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5>
  inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
    RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
  inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
    RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6);
  }
  template <class T0, class T1>
  inline void FLC(T0 &A0, T1 &A1, int x) {
    FLC(A0, x), FLC(A1, x);
  }
  template <class T0, class T1, class T2>
  inline void FLC(T0 &A0, T1 &A1, T2 &A2, int x) {
    FLC(A0, x), FLC(A1, x), FLC(A2, x);
  }
  template <class T0, class T1, class T2, class T3>
  inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) {
    FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x);
  }
  template <class T0, class T1, class T2, class T3, class T4>
  inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) {
    FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5>
  inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) {
    FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
  inline void FLC(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) {
    FLC(A0, x), FLC(A1, x), FLC(A2, x), FLC(A3, x), FLC(A4, x), FLC(A5, x),
        FLC(A6, x);
  }
  template <class T>
  inline void CLR(priority_queue<T> &Q) {
    while (!Q.empty()) Q.pop();
  }
  template <class T>
  inline void CLR(stack<T> &S) {
    while (!S.empty()) S.pop();
  }
  template <class T>
  inline void CLR(queue<T> &Q) {
    while (!Q.empty()) Q.pop();
  }
  template <class T0, class T1>
  inline void CLR(T0 &A0, T1 &A1) {
    CLR(A0), CLR(A1);
  }
  template <class T0, class T1, class T2>
  inline void CLR(T0 &A0, T1 &A1, T2 &A2) {
    CLR(A0), CLR(A1), CLR(A2);
  }
  template <class T0, class T1, class T2, class T3>
  inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) {
    CLR(A0), CLR(A1), CLR(A2), CLR(A3);
  }
  template <class T0, class T1, class T2, class T3, class T4>
  inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) {
    CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5>
  inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) {
    CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5);
  }
  template <class T0, class T1, class T2, class T3, class T4, class T5, class T6>
  inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) {
    CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6);
  }
  template <class T>
  inline void CLR(T &A, int n) {
    for (int i = 0; i < n; ++i) CLR(A[i]);
  }
  template <class T>
  inline bool EPT(T &a) {
    return a.empty();
  }
  template <class T>
  inline T &SRT(T &A) {
    sort(A.begin(), A.end());
    return A;
  }
  template <class T, class C>
  inline T &SRT(T &A, C cmp) {
    sort(A.begin(), A.end(), cmp);
    return A;
  }
  template <class T>
  inline T &RVS(T &A) {
    reverse(A.begin(), A.end());
    return A;
  }
  template <class T>
  inline T &UNQQ(T &A) {
    A.resize(unique(A.begin(), A.end()) - A.begin());
    return A;
  }
  template <class T>
  inline T &UNQ(T &A) {
    SRT(A);
    return UNQQ(A);
  }
  template <class T, class C>
  inline T &UNQ(T &A, C cmp) {
    SRT(A, cmp);
    return UNQQ(A);
  }
  const int MOD = 998244353;
  const int INF = 0x3f3f3f3f;
  const long long INFF = 0x3f3f3f3f3f3f3f3fLL;
  const double EPS = 1e-9;
  const double OO = 1e20;
  const double PI = acos(-1.0);
  const int dx[] = {-1, 1, 0, 0};
  const int dy[] = {0, 0, 1, -1};
  template <class T>
  inline bool checkMin(T &a, const T b) {
    return b < a ? a = b, 1 : 0;
  }
  template <class T>
  inline bool checkMax(T &a, const T b) {
    return a < b ? a = b, 1 : 0;
  }
  template <class T, class C>
  inline bool checkUpd(T &a, const T b, C c) {
    return c(b, a) ? a = b, 1 : 0;
  }
  template <class T>
  inline T min(T a, T b, T c) {
    return min(min(a, b), c);
  }
  template <class T>
  inline T max(T a, T b, T c) {
    return max(max(a, b), c);
  }
  template <class T>
  inline T min(T a, T b, T c, T d) {
    return min(min(a, b), min(c, d));
  }
  template <class T>
  inline T max(T a, T b, T c, T d) {
    return max(max(a, b), max(c, d));
  }
  template <class T>
  inline T min(T a, T b, T c, T d, T e) {
    return min(min(min(a, b), min(c, d)), e);
  }
  template <class T>
  inline T max(T a, T b, T c, T d, T e) {
    return max(max(max(a, b), max(c, d)), e);
  }
  template <class T>
  inline T sqr(T a) {
    return a * a;
  }
  template <class T>
  inline T cub(T a) {
    return a * a * a;
  }
  template <class T>
  inline T ceil(T x, T y) {
    return (x - 1) / y + 1;
  }
  template <class T>
  T abs(T x) {
    return x > 0 ? x : -x;
  }
  inline int sgn(double x) { return x < -EPS ? -1 : x > EPS; }
  inline int sgn(double x, double y) { return sgn(x - y); }
  inline double cos(double a, double b, double c) {
    return (sqr(a) + sqr(b) - sqr(c)) / (2 * a * b);
  }
  inline double cot(double x) { return 1. / tan(x); };
  inline double sec(double x) { return 1. / cos(x); };
  inline double csc(double x) { return 1. / sin(x); };
  namespace BO {
  inline bool _1(int x, int i) { return bool(x & 1 << i); }
  inline bool _1(long long x, int i) { return bool(x & 1LL << i); }
  inline long long _1(int i) { return 1LL << i; }
  inline long long _U(int i) { return _1(i) - 1; };
  inline int reverse_bits(int x) {
    x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
    x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
    x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
    x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
    x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
    return x;
  }
  inline long long reverse_bits(long long x) {
    x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
    x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
    x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
    x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
    x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
    x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
    return x;
  }
  template <class T>
  inline bool odd(T x) {
    return x & 1;
  }
  template <class T>
  inline bool even(T x) {
    return !odd(x);
  }
  template <class T>
  inline T low_bit(T x) {
    return x & -x;
  }
  template <class T>
  inline T high_bit(T x) {
    T p = low_bit(x);
    while (p != x) x -= p, p = low_bit(x);
    return p;
  }
  template <class T>
  inline T cover_bit(T x) {
    T p = 1;
    while (p < x) p <<= 1;
    return p;
  }
  template <class T>
  inline int cover_idx(T x) {
    int p = 0;
    while (_1(p) < x) ++p;
    return p;
  }
  inline int clz(int x) { return __builtin_clz(x); }
  inline int clz(long long x) { return __builtin_clzll(x); }
  inline int ctz(int x) { return __builtin_ctz(x); }
  inline int ctz(long long x) { return __builtin_ctzll(x); }
  inline int lg2(int x) { return !x ? -1 : 31 - clz(x); }
  inline int lg2(long long x) { return !x ? -1 : 63 - clz(x); }
  inline int low_idx(int x) { return !x ? -1 : ctz(x); }
  inline int low_idx(long long x) { return !x ? -1 : ctz(x); }
  inline int high_idx(int x) { return lg2(x); }
  inline int high_idx(long long x) { return lg2(x); }
  inline int parity(int x) { return __builtin_parity(x); }
  inline int parity(long long x) { return __builtin_parityll(x); }
  inline int count_bits(int x) { return __builtin_popcount(x); }
  inline int count_bits(long long x) { return __builtin_popcountll(x); }
  }  // namespace BO
  using namespace BO;
  namespace NT {
  inline long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
  inline long long lcm(long long a, long long b) { return a * b / gcd(a, b); }
  inline void INC(int &a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
  }
  inline int sum(int a, int b) {
    a += b;
    if (a >= MOD) a -= MOD;
    return a;
  }
  inline void DEC(int &a, int b) {
    a -= b;
    if (a < 0) a += MOD;
  }
  inline int dff(int a, int b) {
    a -= b;
    if (a < 0) a += MOD;
    return a;
  }
  inline void MUL(int &a, int b) { a = (long long)a * b % MOD; }
  inline int pdt(int x, int y) {
    int ret;
    __asm__ __volatile__("\tmull %%ebx\n\tdivl %%ecx\n"
                         : "=d"(ret)
                         : "a"(x), "b"(y), "c"(MOD));
    return ret;
  }
  inline int gcd(int m, int n, int &x, int &y) {
    x = 1, y = 0;
    int xx = 0, yy = 1, q;
    while (1) {
      q = m / n, m %= n;
      if (!m) {
        x = xx, y = yy;
        return n;
      }
      DEC(x, pdt(q, xx)), DEC(y, pdt(q, yy));
      q = n / m, n %= m;
      if (!n) return m;
      DEC(xx, pdt(q, x)), DEC(yy, pdt(q, y));
    }
  }
  inline int sum(int a, int b, int c) { return sum(a, sum(b, c)); }
  inline int sum(int a, int b, int c, int d) { return sum(sum(a, b), sum(c, d)); }
  inline int pdt(int a, int b, int c) { return pdt(a, pdt(b, c)); }
  inline int pdt(int a, int b, int c, int d) { return pdt(pdt(a, b), pdt(c, d)); }
  inline int pow(int a, long long b) {
    int c(1);
    while (b) {
      if (b & 1) MUL(c, a);
      MUL(a, a), b >>= 1;
    }
    return c;
  }
  template <class T>
  inline T pow(T a, long long b) {
    T c(1);
    while (b) {
      if (b & 1) c *= a;
      a *= a, b >>= 1;
    }
    return c;
  }
  template <class T>
  inline T pow(T a, int b) {
    return pow(a, (long long)b);
  }
  inline int _I(int b) {
    int a = MOD, x1 = 0, x2 = 1, q;
    while (1) {
      q = a / b, a %= b;
      if (!a) return x2;
      DEC(x1, pdt(q, x2));
      q = b / a, b %= a;
      if (!b) return x1;
      DEC(x2, pdt(q, x1));
    }
  }
  inline void DIV(int &a, int b) { MUL(a, _I(b)); }
  inline int qtt(int a, int b) { return pdt(a, _I(b)); }
  struct Int {
    int val;
    operator int() const { return val; }
    Int(int _val = 0) : val(_val) {
      val %= MOD;
      if (val < 0) val += MOD;
    }
    Int(long long _val) : val(_val) {
      _val %= MOD;
      if (_val < 0) _val += MOD;
      val = _val;
    }
    Int &operator+=(const int &rhs) {
      INC(val, rhs);
      return *this;
    }
    Int operator+(const int &rhs) const { return sum(val, rhs); }
    Int &operator-=(const int &rhs) {
      DEC(val, rhs);
      return *this;
    }
    Int operator-(const int &rhs) const { return dff(val, rhs); }
    Int &operator*=(const int &rhs) {
      MUL(val, rhs);
      return *this;
    }
    Int operator*(const int &rhs) const { return pdt(val, rhs); }
    Int &operator/=(const int &rhs) {
      DIV(val, rhs);
      return *this;
    }
    Int operator/(const int &rhs) const { return qtt(val, rhs); }
    Int operator-() const { return MOD - *this; }
  };
  }  // namespace NT
  using namespace NT;
  template <class T>
  inline T &RD(T &x) {
    char c;
    while (!isdigit((c = getchar())))
      ;
    x = c - '0';
    while (isdigit((c = getchar()))) x = x * 10 + c - '0';
    return x;
  }
  template <class T>
  inline T &RDD(T &x) {
    char c;
    while ((c = getchar()), c != '-' && !isdigit(c))
      ;
    if (c == '-') {
      x = '0' - (c = getchar());
      while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
    } else {
      x = c - '0';
      while (isdigit((c = getchar()))) x = x * 10 + c - '0';
    }
    return x;
  }
  inline double &RF(double &x) {
    char c;
    while ((c = getchar()), c != '-' && c != '.' && !isdigit(c))
      ;
    if (c == '-')
      if ((c = getchar()) == '.') {
        x = 0;
        double l = 1;
        while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
        x *= l;
      } else {
        x = '0' - c;
        while (isdigit((c = getchar()))) x = x * 10 + '0' - c;
        if (c == '.') {
          double l = 1;
          while (isdigit((c = getchar()))) l /= 10, x = x * 10 + '0' - c;
          x *= l;
        }
      }
    else if (c == '.') {
      x = 0;
      double l = 1;
      while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
      x *= l;
    } else {
      x = c - '0';
      while (isdigit((c = getchar()))) x = x * 10 + c - '0';
      if (c == '.') {
        double l = 1;
        while (isdigit((c = getchar()))) l /= 10, x = x * 10 + c - '0';
        x *= l;
      }
    }
    return x;
  }
  inline char *RS(char *s) {
    scanf("%s", s);
    return s;
  }
  long long last_ans;
  int Case;
  template <class T>
  inline void OT(const T &x) {
    cout << x << endl;
  }
  const int N = int(5e5) + 9;
  namespace BIT {
  int C[N], n;
  int Sum(int x) {
    int z = 0;
    for (; x; x ^= low_bit(x)) z += C[x];
    return z;
  }
  void Add(int x, int d) {
    for (; x <= n; x += low_bit(x)) C[x] += d;
  }
  int Sum(int l, int r) { return Sum(r) - Sum(l - 1); }
  }  // namespace BIT
  using namespace BIT;
  int main() {
    for (int ____T = RD(); ____T--;) {
      RD(n);
      long long z = 0;
      set<int> H;
      bool ok = 0;
      for (int i = 0; i < n; ++i) {
        int a;
        RD(a);
        z += i - Sum(a);
        if ((H.find(a) != H.end())) ok = true;
        Add(a, 1);
        H.insert(a);
      }
      if (ok) z = 0;
      for (int i = 1; i <= n; ++i) C[i] = 0;
      puts((z & 1) ? "NO" : "YES");
    }
  }
  