Sorting

#include <bits/stdc++.h>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    set<vi> bad;
    for1(n, 4) {
        vvi allp;
        vi perm(n);
        iota(all(perm), 0);
        do {
            allp.pb(perm);
        } while (next_permutation(all(perm)));

        set<vi> vis = {allp[0]};
        vvi q = {allp[0]};

        forn(cur, q.size()) {
            vi v = q[cur];
            forn(i, n - 1) forn(j, i - 1) {
                vi u = v;
                swap(u[j], u[i]);
                swap(u[j + 1], u[i + 1]);
                if (vis.count(u)) continue;
                vis.insert(u);
                q.pb(u);
            }
        }

        for (auto &v: allp) if (!vis.count(v)) {
            bad.insert(v);
        }
    }

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vi a(n);
        forn(i, n) cin >> a[i], --a[i];
        bool ok;
        if (n <= 4) ok = !bad.count(a);
        else {
            int inv = 0;
            forn(i, n) forn(j, i) if (a[j] > a[i]) ++inv;
            ok = inv % 2 == 0;
        }
        cout << (ok ? "YES" : "NO") << '\n';
    }

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED