Sorting

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef pair<ld,ld> state;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

void solve_slow(int n)
{
	set<vi> S;
	vi p(n);
	for(int i=0;i<n;i++) p[i]=i;
	S.insert(p);
	queue<vi> q; q.push(p);
	while(!q.empty())
	{
		vi f = q.front(); q.pop();
		for(int i=0;i<n;i++)
		{
			for(int j=i+2;j+1<n;j++)
			{
				swap(f[i],f[j]);
				swap(f[i+1],f[j+1]);
				if(S.find(f)==S.end())
				{
					S.insert(f);
					q.push(f);
				}
				swap(f[i],f[j]);
				swap(f[i+1],f[j+1]);
			}
		}
	}
	for(auto v:S)
	{
		for(int x:v) cout<<x+1<<' ';
		cout<<'\n';
	}
	cout<<S.size()<<'\n';
}

void solve()
{
	int n; cin>>n;
	vi a(n);
	for(int i=0;i<n;i++) cin>>a[i];
	if(n<=3)
	{
		bool pos=1;
		for(int i=0;i<n;i++)
		{
			if(a[i]!=i+1){pos=0; break;}
		}
		cout<<(pos?"YES":"NO")<<'\n';
		return ;
	}
	vi iden = {1,2,3,4};
	vi lul = {3,4,1,2};
	if(n<=4)
	{
		if(a==iden||a==lul)
		{
			cout<<"YES\n";
		}
		else
		{
			cout<<"NO\n";
		}
		return ;
	}
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		for(int j=i+1;j<n;j++)
		{
			if(a[i]>a[j]) cnt++;
		}
	}
	cout<<(cnt%2==0?"YES":"NO")<<'\n';
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	//int n; cin>>n; solve_slow(n); return 0;
	int t; cin>>t;
	while(t--) solve();
}

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