Sorting

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define TR(X) ({ if(1) cerr << "TR: " << (#X) << " = " << (X) << endl; })
 
void brute(ll n) {
	set<vl> reach;
 
	vl p(n);
	iota(all(p),1);
 
	queue<vl> q;
	q.push(p), reach.insert(p);
 
	while (sz(q)) {
		p = q.front();
		q.pop();
		
		FOR(i,0,n) FOR(j,i+2,n-1) {
			vl np = p;
			swap(np[i],np[j]);
			swap(np[i+1],np[j+1]);
			if (reach.count(np)) continue;
			q.push(np), reach.insert(np);
		}
	}
	
	for (vl p: reach) {
		for (ll x: p) cout << x << " ";
		cout << endl;
	}
	cout << endl << sz(reach) << endl;
}
 
bool solve(vl p) {
	ll n = sz(p);
	if (n <= 3) return is_sorted(all(p));
	if (n == 4) return p == vl{1,2,3,4} || p == vl{3,4,1,2};
 
	ll invs = 0;
	FOR(i,0,n) FOR(j,i+1,n) invs += p[i] > p[j];
	return invs%2 == 0;
}
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	ll tc; cin >> tc;
	while (tc--) {
		ll n; cin >> n;
		vl p(n);
		FOR(i,0,n) cin >> p[i];
		cout << (solve(p) ? "YES" : "NO") << endl;
	}
 
}
 

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