CF2226D

对于相邻的奇数和偶数，它们可以随便交换位置。

将序列的奇数和偶数分别考虑，因为只要奇数有序且偶数有序，就一定可以通过交换得到一个有序的序列。

对于奇数，两个相邻的奇数想要交换顺序，那么就一定需要一个偶数作为最大值或者最小值。

对于偶数，也是同理。

所以我们观察全局最大和最小值。

如果这两个值是一奇一偶，假设最大值是奇数，最小值是偶数。

那么任意两个相邻的奇数都可以通过这个最小值进行相对位置的交换，偶数同理。

如果两个值的奇偶性相同，假如是两个奇数。

那么所有的偶数一定可以排成有序。

此时设偶数最小值为 $L$，最大值为 $R$

对于奇数，值在 $[L, R]$ 范围的都可以通过偶数来进行排序。

所以我们需要检查 $< L$ 的奇数和 $>R$ 的奇数是否天然有序，因为这两个集合中的数没办法通过任何呀一个跳板进行交换。

还有一种情况需要特判，没有奇数或者偶数，那么除非它天然有序，否则不可行。

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 7;
using ll = long long;
#define fi first
#define se second
using pii = pair<int, int>;

void solve() {
  int n;
  cin >> n;
  vector<vector<pii>> num(2);
  int maxn = -INF, minn = INF;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    maxn = max(maxn, x), minn = min(minn, x);
    if (x & 1)
      num[1].emplace_back(x, i);
    else
      num[0].emplace_back(x, i);
  }
  int maxp = -INF, minp = INF;
  if ((maxn ^ minn) & 1) {
    cout << "YES" << '\n';
  } else {
    bool flag = (maxn & 1);
    if (num[flag ^ 1].size()) {
      for (auto [i, idx] : num[flag ^ 1]) {
        maxp = max(maxp, i), minp = min(minp, i);
      }
    } else {
      for (int i = 0; i < num[flag].size() - 1; i++) {
        if (num[flag][i].fi > num[flag][i + 1].fi)
          return void(cout << "NO" << '\n');
      }
      return void(cout << "YES" << '\n');
    }
    int L = -1, R = n;
    for (auto [i, idx] : num[flag]) {
      if (i < minp) L = max(L, idx);
      if (i > maxp) R = min(R, idx);
    }
    if (L > R)
      cout << "NO" << '\n';
    else
      cout << "YES" << '\n';
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int T;
  cin >> T;
  while (T--) solve();
  return 0;
}