Sorting

/*input
3
2
1 2
5
2 3 5 1 4
4
2 4 3 1
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using ordered_map = tree<T, X, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename X>
using fast_map = cc_hash_table<T, X>;
//using ull = __uint128_t;
using ull = unsigned long long;
using ll = long long;
using ld = long double;
mt19937_64 rng(123);
const ll mod = 1000000007;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	set<ll>A[10];
	for (int n = 1; n <= 8; n++)
	{
		int p[n + 1];
		p[0] = 0;
		for (int i = 1; i <= n; i++)
			p[i] = i;
		function<void()> dfs = [&]()
		{
			ll v = 0;
			for (int i = 1; i <= n; i++)
			{
				v *= 8;
				v += p[i];
			}
			if (A[n].count(v))
				return;
			A[n].insert(v);
			for (int a = 1; a + 3 <= n; a++)
			{
				for (int b = a + 2; b < n; b++)
				{
					swap(p[a], p[b]);
					swap(p[a + 1], p[b + 1]);
					dfs();
					swap(p[a], p[b]);
					swap(p[a + 1], p[b + 1]);
				}
			}
		};
		dfs();
	}
	while (t--)
	{
		int n;
		cin >> n;
		int p[n + 1];
		p[0] = 0;
		for (int i = 1; i <= n; i++)
			cin >> p[i];
		if (n <= 8)
		{
			ll v = 0;
			for (int i = 1; i <= n; i++)
			{
				v *= 8;
				v += p[i];
			}
			if (A[n].count(v))
				cout << "YES\n";
			else
				cout << "NO\n";
		}
		else
		{
			ll s = 0;
			for (int i = 1; i <= n; i++)
				for (int j = 1; j < i; j++)
					if (p[j] > p[i])
						s++;
			if (s % 2 == 1)
				cout << "NO\n";
			else {
				cout << "YES\n";
			}
		}
	}
}

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