#include "library3.h"
#include <bits/stdc++.h>
std::mt19937 rng(time(0));
int la,cnt=0;
std::vector<int> sv(std::vector<int> b,std::vector<int> tp) {
	if(tp.size()<=1) return b;
	for(int j=0;j<tp.size();j++) {
		std::swap(tp[j],tp[rng()%(j+1)]);
	}
	std::swap(b[tp[0]],b[tp[1]]);
	la--;
	std::vector<int> t0,t1;
	t0.push_back(tp[0]);
	t1.push_back(tp[1]);
	for(int j=2;j<tp.size();j++) {
		std::swap(b[tp[0]],b[tp[j]]);
		cnt++;assert(cnt<=5000);
		if(query(b)<=la) {
			t0.push_back(tp[j]);
		} else {			
			t1.push_back(tp[j]);
		}
		std::swap(b[tp[0]],b[tp[j]]);
	}
	b=sv(b,t0);
	b=sv(b,t1);
	return b;
}
void solve(int N) {
	std::vector<int> b,b2;
	b.resize(N);b2.resize(N);
	for(int i=0;i<N;i++) {
		b[i]=i;b2[i]=i;
	}
	la=query(b);
	for(int i=0;i<N;i++) {
		std::vector<int> xx=b;
		int l=0,r=i,mm;
		while(l<r) {
			mm=(l+r)/2;
			for(int j=mm;j<i;j++) {
				std::swap(b[i],b[j]);
			}
			if(query(b)==la+(i-mm)) {
				r=mm;
			} else {
				l=mm+1;
			}
			b=xx;
		}
		if(l) {
			std::swap(b[i],b[l-1]);
			la--;
			assert(la==query(b));
		}
	}
	answer(b);
	return;
	for(int i=0;i<N;i++) {		
		std::swap(b[i],b[rng()%(i+1)]);
		std::swap(b2[i],b2[rng()%(i+1)]);
	}
	la=query(b);
	bool vi[509]={0};
	int ct=N;
	for(int i=0;i<N;i++) {
		if(vi[i]) continue;
		std::vector<int> tp;
		tp.push_back(b2[i]);
		for(int j=i+1;j<N;j++) {
			if(vi[j]) continue;
			if(la==ct-1) {
				tp.push_back(b2[j]);
				vi[j]=1;
				continue;
			} 
			std::swap(b[b2[i]],b[b2[j]]);
			cnt++;assert(cnt<=5000);
			if(query(b)<la) {
				tp.push_back(b2[j]);
				vi[j]=1;
				std::swap(b[b2[i]],b[b2[j]]);
				continue;
			} 
			std::swap(b[b2[i]],b[b2[j]]);
		}
		ct-=tp.size();
		b=sv(b,tp);
	}
	answer(b);
}