#include "library3.h"
#include <bits/stdc++.h>
std::mt19937 rng(time(0));
int la;
std::vector<int> sv2(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]]);
		if(query(b)<=la) {
			t0.push_back(tp[j]);
		} else {			
			t1.push_back(tp[j]);
		}
		std::swap(b[tp[0]],b[tp[j]]);
	}
	b=sv2(b,t0);
	b=sv2(b,t1);
	return b;
}
std::vector<int> sv(std::vector<int> b,std::vector<int> tp,int vv) {
	if(tp.size()<=1) return b;
	for(int j=0;j<tp.size();j++) {
		std::swap(tp[j],tp[rng()%(j+1)]);
	}
	for(int j=0;j<tp.size();j++) {
		std::swap(b[tp[j]],b[tp[rng()%(j+1)]]);
	}
	bool vi[509]={0};
	int aa=query(b),ta=aa,cnt=tp.size();
	for(int i=0;i<tp.size();i++) {
		if(vi[i]) continue;
		std::vector<int> tp2;
		tp2.push_back(tp[i]);
		for(int j=i+1;j<tp.size();j++) {
			if(vi[j]) continue;
			std::swap(b[tp[i]],b[tp[j]]);
			if((vv==aa-cnt+1)||(query(b)<aa)) {
				tp2.push_back(tp[j]);
				vi[j]=1;
			}
			std::swap(b[tp[i]],b[tp[j]]);
		}
		la=aa;
		cnt-=tp2.size();
		if(tp2.size()<=500) b=sv2(b,tp2);
		else b=sv(b,tp2,aa);
		aa-=tp2.size()-1;
	}
	return b;
}
void solve(int N) {
	std::vector<int> b;
	std::vector<int> tp;
	b.resize(N);
	tp.resize(N);
	for(int i=0;i<N;i++) {
		b[i]=i;
		tp[i]=i;
	}
	answer(sv(b,tp,0));
	return;
/*	for(int i=0;i<N;i++) {		
		std::swap(b[i],b[rng()%(i+1)]);
	}
	la=query(b);
	int cq=0;
	while(la<N-1) {
		int x=rng()%N,y=rng()%N;
		if(x==y) continue;
		std::swap(b[x],b[y]);
		cq++;
		int ak=query(b);
		if(la<ak) {
			la=ak;
		} else {
			std::swap(b[x],b[y]);
		}
	}
	printf("%d\n",cq);
	std::vector<int> tp;
	for(int i=0;i<N;i++) tp.push_back(i);
	answer(sv(b,tp));
	return;
	bool vi[509]={0};
	int cnt=N;
	for(int i=0;i<N;i++) {
		if(vi[i]) continue;
		std::vector<int> tp;
		tp.push_back(i);
		for(int j=i+1;j<N;j++) {
			if(vi[j]) continue;
			std::swap(b[i],b[j]);
			if((la==cnt-1)||(query(b)<la)) {
				tp.push_back(j);
				vi[j]=1;
			}
			std::swap(b[i],b[j]);
		}
		cnt-=tp.size();
		b=sv(b,tp);
	}
	answer(b);*/
}