Sorting

input/code.cpp: In lambda function:
input/code.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l+r>>1;
           ~^~

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// if you're reading this i hope to meet you in IOI 2021
// RECHECK CONSTRAINTS AFTER MAKING A REDUCTION

void solve() {
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	if (n == 4) {
		cout << (arr == vector<int>{1, 2, 3, 4} or arr == vector<int>{3, 4, 1, 2} ? "YES" : "NO") << endl;
		return;
	}
	if (n < 4) {
		for (int i = 0; i < n; i++)
			if (arr[i] != i+1) {
				cout << "NO\n";
				return;
			}
		cout << "YES\n";
		return;
	}

	function<ll(int, int)> inv = [&](int l, int r) -> ll {
		if (r-l == 1) return 0;
		int m = l+r>>1;
		ll res = inv(l, m) + inv(m, r);
		for (int i = l; i < m; i++)
			res += lower_bound(arr.begin()+m, arr.begin()+r, arr[i])-(arr.begin()+m);
		sort(arr.begin()+l, arr.begin()+r);
		return res;
	};
	
	cout << (inv(0, n)&1 ? "NO" : "YES") << endl;
}

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) solve();
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

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