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;
	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)
		{
			bool ok = false;
			set<ll>A;
			function<void()> dfs = [&]()
			{
				ll v = 0;
				for (int i = 1; i <= 8; i++)
				{
					v += p[i];
					v *= 8;
				}
				if (A.count(v))
					return;
				A.insert(v);
				if (ok)
					return;
				if (is_sorted(p + 1, p + n + 1)) {
					ok = true;
					return;
				}
				for (int a = 1; a < 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();
			if (ok)
				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: TIME LIMIT EXCEEDED