Sorting

///By Stephan Ramirez dsramirezc@unal.edu.co
#include<bits/stdc++.h>
#define ms(a,v) memset(a,v,sizeof a)
#define ll long long
#define N 105
#define MAXN 20004
using namespace std;
int T;
int n;
int arr[N];
int pos[N];
void sw(int x,int y){
	swap(arr[x],arr[y]);
	swap(arr[x+1],arr[y+1]);
	pos[arr[x]]=x;
	pos[arr[x+1]]=x+1;
	pos[arr[y]]=y;
	pos[arr[y+1]]=y+1;
}
const int range_from  = 0;
const int range_to    = 100;
std::random_device                  rand_dev;
std::mt19937                        generator(rand_dev());
std::uniform_int_distribution<int>  distr(range_from, range_to);
int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	#ifdef LOCAL
		freopen("in.txt","r",stdin);
		//freopen("out.txt","w",stdout)	;
	#endif
	cin>>T;
	while(T--){
		cin>>n;
		for(int i=0;i<n;i++){
			cin>>arr[i];
			arr[i]--;
			pos[arr[i]]=i;
		}
		bool f=false;
		
		for(int j=0;j<200;j++){
			for(int i=0;i<100;i++){
				
				int l=distr(generator)%n;
				int r=distr(generator)%n;
				if(l>r)
					swap(l,r);
				if(l+1<r && r<n-1)
					sw(l,r);
			}
			for(int i=0;i<n;i++){
				if(pos[i]==i){
					if(i==n-1){
						f=true;
						break;
					}
					continue;
				}
				if(pos[i]==i+1){
					if(i+3<n-1){
						sw(i+1,i+3);
						i--;
						continue;
					}
					break;
				}
				if(pos[i]==n-1){
					if(i<=n-4){
							sw(n-4,n-2);
							i--;
							continue;
					}
					break;
				}
				sw(pos[i],i);
				i--;
			}
			if(f)
				break;
		}
		if(f)
			cout<<"YES\n";
		else
			cout<<"NO\n";
	}
	return 0;
}
 

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