#include <bits/stdc++.h>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::greater;
using std::less;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multiset;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::unique;
using std::unordered_map;
using std::upper_bound;
using std::vector;
template <typename T>
void in(T &x) {
  x = 0;
  bool f = false;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  if (f) x = -x;
}
template <typename T>
void out(T x, char ch = '\n') {
  static int tp, sk[30];
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  do {
    sk[++tp] = x % 10;
    x /= 10;
  } while (x);
  while (tp) {
    putchar(sk[tp--] + '0');
  }
  putchar(ch);
}
template <typename T>
void Mx(T &x, T y) {
  x < y && (x = y);
}
template <typename T>
void Mn(T &x, T y) {
  x > y && (x = y);
}
template <typename T>
T sabs(T x) {
  return x < 0 ? -x : x;
}
namespace Mod {
const int md = 998244353;
inline int add(const int &a, const int &b) {
  int p = a + b;
  if (p >= md) p -= md;
  return p;
}
inline int sub(const int &a, const int &b) {
  int p = a - b;
  if (p < 0) p += md;
  return p;
}
inline int mul(const int &a, const int &b) { return 1ll * a * b % md; }
inline int qpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) ret = mul(ret, a);
  return ret;
}
inline int inv(int x) { return qpow(x, md - 2); }
}  // namespace Mod
using Mod::add;
using Mod::inv;
using Mod::md;
using Mod::mul;
using Mod::qpow;
using Mod::sub;
const int N = 500010;
int n;
int a[N], c[N];
void Insert(int x) {
  for (; x <= n; x += x & -x) ++c[x];
}
int query(int x) {
  int ret = 0;
  for (; x; x -= x & -x) ret += c[x];
  return ret;
}
namespace gvihvo {
void main() {
  in(n);
  map<int, int> cnt;
  for (int i = 1; i <= n; ++i) {
    in(a[i]);
    ++cnt[a[i]];
  }
  for (auto i : cnt)
    if (i.second > 1) {
      puts("YES");
      return;
    }
  long long val = 0;
  for (int i = n; i >= 1; --i) {
    val += query(a[i]);
    Insert(a[i]);
  }
  val % 2 ? puts("NO") : puts("YES");
  memset(c, 0, sizeof(int) * (n + 10));
}
}  // namespace gvihvo
int main() {
  int cza;
  scanf("%d", &cza);
  while (cza--) gvihvo::main();
  return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::greater;
using std::less;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multiset;
using std::pair;
using std::priority_queue;
using std::queue;
using std::set;
using std::sort;
using std::string;
using std::swap;
using std::unique;
using std::unordered_map;
using std::upper_bound;
using std::vector;
template <typename T>
void in(T &x) {
  x = 0;
  bool f = false;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  if (f) x = -x;
}
template <typename T>
void out(T x, char ch = '\n') {
  static int tp, sk[30];
  if (x < 0) {
    putchar('-');
    x = -x;
  }
  do {
    sk[++tp] = x % 10;
    x /= 10;
  } while (x);
  while (tp) {
    putchar(sk[tp--] + '0');
  }
  putchar(ch);
}
template <typename T>
void Mx(T &x, T y) {
  x < y && (x = y);
}
template <typename T>
void Mn(T &x, T y) {
  x > y && (x = y);
}
template <typename T>
T sabs(T x) {
  return x < 0 ? -x : x;
}
namespace Mod {
const int md = 998244353;
inline int add(const int &a, const int &b) {
  int p = a + b;
  if (p >= md) p -= md;
  return p;
}
inline int sub(const int &a, const int &b) {
  int p = a - b;
  if (p < 0) p += md;
  return p;
}
inline int mul(const int &a, const int &b) { return 1ll * a * b % md; }
inline int qpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = mul(a, a))
    if (b & 1) ret = mul(ret, a);
  return ret;
}
inline int inv(int x) { return qpow(x, md - 2); }
}  // namespace Mod
using Mod::add;
using Mod::inv;
using Mod::md;
using Mod::mul;
using Mod::qpow;
using Mod::sub;
const int N = 500010;
int n;
int a[N], c[N];
void Insert(int x) {
  for (; x <= n; x += x & -x) ++c[x];
}
int query(int x) {
  int ret = 0;
  for (; x; x -= x & -x) ret += c[x];
  return ret;
}
namespace gvihvo {
void main() {
  in(n);
  map<int, int> cnt;
  for (int i = 1; i <= n; ++i) {
    in(a[i]);
    ++cnt[a[i]];
  }
  for (auto i : cnt)
    if (i.second > 1) {
      puts("YES");
      return;
    }
  long long val = 0;
  for (int i = n; i >= 1; --i) {
    val += query(a[i]);
    Insert(a[i]);
  }
  val % 2 ? puts("NO") : puts("YES");
  memset(c, 0, sizeof(int) * (n + 10));
}
}  // namespace gvihvo
int main() {
  int cza;
  scanf("%d", &cza);
  while (cza--) gvihvo::main();
  return 0;
}

```