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;
  mt19937 rnd;
  struct node {
    node *l = 0, *r = 0;
    int x, y, siz;
    node(int x) : x(x), y(rnd()), siz(1) {}
  };
  int size(node *t) {
    if (!t) return 0;
    return t->siz;
  }
  void update(node *t) { t->siz = size(t->l) + size(t->r) + 1; }
  pair<node *, node *> split(node *t, int x) {
    if (!t) return {0, 0};
    if (t->x <= x) {
      auto p = split(t->r, x);
      t->r = p.first;
      update(t);
      return {t, p.second};
    } else {
      auto p = split(t->l, x);
      t->l = p.second;
      update(t);
      return {p.first, t};
    }
  }
  node *merge(node *a, node *b) {
    if (!a) return b;
    if (!b) return a;
    if (a->y > b->y) {
      a->r = merge(a->r, b);
      update(a);
      return a;
    } else {
      b->l = merge(a, b->l);
      update(b);
      return b;
    }
  }
  node *insert(node *t, node *in) {
    if (!t) return in;
    if (in->y > t->y) {
      auto p = split(t, in->x);
      in->l = p.first;
      in->r = p.second;
      update(in);
      return in;
    }
    if (in->x < t->x) {
      t->l = insert(t->l, in);
    } else {
      t->r = insert(t->r, in);
    }
    update(t);
    return t;
  }
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    for (int useless = 0; useless < t; useless++) {
      int n;
      cin >> n;
      vector<int> a(n);
      for (int i = 0; i < n; i++) cin >> a[i];
      node *t = 0;
      vector<int> a_srt(n);
      copy(a.begin(), a.end(), a_srt.begin());
      sort(a_srt.begin(), a_srt.end());
      bool good = false;
      for (int i = 1; i < n; i++) {
        if (a_srt[i] == a_srt[i - 1]) {
          cout << "YES\n";
          good = true;
          break;
        }
      }
      if (good) continue;
      bool dp_all = true;
      t = insert(t, new node(a[0]));
      for (int i = 1; i < n; i++) {
        auto p = split(t, a[i]);
        if (size(p.second) % 2) {
          dp_all = !dp_all;
        }
        t = merge(p.first, p.second);
        t = insert(t, new node(a[i]));
      }
      if (dp_all)
        cout << "YES\n";
      else
        cout << "NO\n";
    }
  }
  