//code by Nobody.Emissary
#include "monster.h"
#include<bits/stdc++.h>

using namespace std;

const int MAXN = 100002;

int p[MAXN], q[MAXN], a[MAXN], n, op[15][15];

bool Query(int,int);
/*
bool Query(int x, int y){
	return a[x]==a[y]-1 || a[x]>a[y]+1;
}*/

inline void MergeSort(int l, int r){
	if(l==r) return ;
	int mid=(l+r)>>1;
	MergeSort(l,mid); MergeSort(mid+1,r);
	int i=l, j=mid+1, now=l;
	while(i<=mid && j<=r){
		if(Query(p[i],p[j])) q[now]=p[j], ++now, ++j;
		else q[now]=p[i], ++now, ++i;
	}
	while(i<=mid) q[now]=p[i], ++now, ++i;
	while(j<=r) q[now]=p[j], ++now, ++j;
	for(int i=l;i<=r;++i) p[i]=q[i];
	return ;
}

vector<int> Solve(int N){
	vector<int> res;
	for(int i=0;i<N;++i) p[i]=i;
	MergeSort(0,N-1);
	//for(int i=0;i<N;++i) cout << p[i] << ' '; cout << endl;
	for(int i=0;i<min(N,10);++i)
		for(int j=i+1;j<min(N,10);++j) op[i][j]=Query(p[i],p[j]);
	int zero=-1; vector<int> pos;
	for(int i=0;i<min(N,10);++i){
		int tot=0;
		for(int j=0;j<i;++j) tot+=!op[j][i];
		for(int j=i+1;j<min(N,10);++j) tot+=op[i][j];
		if(tot==1) pos.push_back(i);
	}
	if(pos.size()==1) zero=pos[0];
	else{
		if(Query(p[pos[0]],p[pos[1]])) zero=pos[0];
		else zero=pos[1];
	}
	//cerr << "zero:" << zero << ' ' << endl;
	reverse(p,p+1+zero); int las=zero;
	for(int i=zero+1;i<N;++i){
		if(Query(p[las],p[i])){
			reverse(p+las+1,p+i+1);
			las=i;
		}
	}
	//for(int i=0;i<N;++i) cout << p[i] << ' '; cout << endl;
	for(int i=0;i<N;++i) q[p[i]]=i;
	for(int i=0;i<N;++i) res.push_back(q[i]);
	return res;
}
/*
int main(){
	srand(time(0));
	cin >> n;
	for(int i=0;i<n;++i) a[i]=i;
	random_shuffle(a,a+n);
	vector<int> ans=Solve(n);
	for(auto i:ans) cout << i << ' '; cout << endl;
	for(int i=0;i<n;++i) cout << a[i] << ' '; cout << endl;
	return 0;
}*/