#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;
}

### Prompt

In CPP, your task is to solve the following problem:

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 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;
}

```