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>
  using namespace std;
  void speed() {
    cin.tie(0);
    cin.sync_with_stdio(0);
  }
  long long factorial(long long x) {
    long long res = 1;
    for (int i = 2; i <= x; i++) {
      res *= i;
    }
    return res;
  }
  long long remove_0(long long x) {
    long long res = 0, cnt = 1;
    while (x > 0) {
      int digit = x % 10;
      if (digit != 0) {
        res += (digit * cnt);
        cnt *= 10;
      }
      x /= 10;
    }
    return res;
  }
  bool prime[100005];
  void prime_numbers(int x) {
    memset(prime, true, sizeof(prime));
    int c = 0;
    prime[0] = prime[1] = false;
    for (int i = 2; i * i <= 100001; i++) {
      if (prime[i] == true) {
        for (int j = i * i; j <= 100001; j += i) {
          prime[j] = false;
        }
      }
    }
    return;
  }
  long long sum_binary(long long x) {
    long long s = 0;
    while (x > 0) {
      s += x % 2;
      x /= 2;
    }
    return s;
  }
  int binary_s(int a[], int l, int h, int k) {
    if (l <= h) {
      int mid = (l + h) / 2;
      if (k == a[mid]) return mid;
      if (k < a[mid]) {
        return binary_s(a, l, mid - 1, k);
      } else
        return binary_s(a, mid + 1, h, k);
    } else
      return -1;
  }
  void bubble_sort(char x[], int n) {
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (x[j] > x[j + 1]) {
          char temp = x[j];
          x[j] = x[j + 1];
          x[j + 1] = temp;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      cout << x[i];
    }
    cout << '\n';
  }
  long long npr(int n, int r) {
    long long res = 1;
    for (int i = n - r + 1; i <= n; i++) {
      res *= i;
    }
    return res;
  }
  long long cper(int n, int r) {
    long long res = 1;
    for (int i = n - r + 1; i <= n; i++) {
      res *= i;
      if (res % r == 0) {
        res /= r;
        r = 1;
      }
    }
    return res;
  }
  long long ncr(int n, int r) { return npr(n, r) / factorial(r); }
  long long sum(long long x) { return x * (x + 1) / 2; }
  long long gcd(long long int a, long long int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  long long lcm(int a, int b) { return (a / gcd(a, b)) * b; }
  long long mod = 1e9 + 7;
  long long ipow(long long a, long long b) {
    long long answer = 1;
    for (; b--;) {
      answer *= a;
      answer %= mod;
    }
    return answer % mod;
  }
  int ipow(int a, int b) {
    int answer = 1;
    for (; b--;) answer *= a;
    return answer;
  }
  long long xorSum(int arr[], int n) {
    int bits = 0;
    for (int i = 0; i < n; ++i) bits |= arr[i];
    long long ans = bits * pow(2, n - 1);
    ans %= mod;
    return ans;
  }
  __int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      if (ch == '-') f = -1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + ch - '0';
      ch = getchar();
    }
    return x * f;
  }
  void print(__int128 x) {
    if (x < 0) {
      putchar('-');
      x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
  }
  __int128 f(long long x) {
    __int128 res = 1;
    for (__int128 i = 2; i <= x; i++) {
      res *= i;
    }
    return res;
  }
  int main() {
    speed();
    int t, n, arr3[500005];
    static pair<int, int> arr1[500005], arr[500005];
    cin >> t;
    bool no;
    bool yes;
    while (t--) {
      cin >> n;
      no = 0;
      yes = 0;
      for (int i = 1; i <= n; i++) arr3[i] = 0;
      for (int i = 1; i <= n; i++) {
        cin >> arr[i].first;
        arr1[i] = {arr[i].first, i};
        arr3[arr[i].first]++;
      }
      for (int i = 1; i <= n; i++)
        if (arr3[i] > 1) yes = 1;
      if (yes) {
        cout << "YES" << '\n';
        continue;
      }
      sort(arr1 + 1, arr1 + 1 + n);
      for (int i = 1; i <= n; i++) {
        arr[arr1[i].second].second = i;
      }
      for (int i = n; i > 2; i--) {
        pair<int, int> temp;
        if (arr1[i].second != i) {
          temp = arr[i];
          arr[i] = {arr1[i].first, i};
          if (temp.second != i - 1) {
            arr[arr1[i].second] = {arr1[i - 1].first, i - 1};
            arr[arr1[i - 1].second] = temp;
            arr1[temp.second].second = arr1[i - 1].second;
            arr1[i - 1].second = arr1[i].second;
          } else {
            arr[arr1[i].second] = {arr1[i - 2].first, i - 2};
            arr[arr1[i - 2].second] = temp;
            arr1[temp.second].second = arr1[i - 2].second;
            arr1[i - 2].second = arr1[i].second;
          }
        }
      }
      for (int i = 1; i < n; i++) {
        if (arr[i].first > arr[i + 1].first) {
          no = 1;
        }
      }
      if (n >= 3 && arr[1].first == arr[3].first && arr[1] > arr[2]) no = 0;
      if (no)
        cout << "NO" << '\n';
      else
        cout << "YES" << '\n';
    }
    return 0;
  }
  