#include "art.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using ar2 = array<int,2>;
using ar3 = array<int,3>;
using ll = long long;
const int mxN = 4010;

int n;
vector<int> v;
bool better[mxN];
map<vector<int>,int> M;

int myPublish(vector<int> V){
	if(M.count(V)) return M[V];
	return M[V] = publish(V);
}

void recur(int l, int r){
	if(l==r) return;
	
	int xd = (r-l+1);
	for(int i = l; i <= r; i++) 
		better[v[i]]=0;
	int st = myPublish(v);
	if(st==0) return;
	int cnt = 0;
	while(xd-- and cnt<=(r-l+1)/2){
		int b = v[r];
		v.erase(begin(v)+r);
		v.insert(begin(v)+l,b);
		int now = myPublish(v);
		if(now <= st) better[b]=1,cnt++;
		st = now;
	}
	vector<int> nw; nw.clear();
	for(int i = 0; i < l; i++) nw.pb(v[i]);
	for(int i = l; i <= r; i++) if(better[v[i]]) nw.pb(v[i]);
	for(int i = l; i <= r; i++) if(!better[v[i]]) nw.pb(v[i]);
	for(int i = r+1; i < n; i++) nw.pb(v[i]);
	v.clear(); for(auto u : nw) v.pb(u);
	int mid = (l+r)/2; recur(l,mid); recur(mid+1,r);
}

void solve(int N) {
	n = N; srand(time(NULL));
	v.resize(N,0);
    iota(all(v),1);
    random_shuffle(all(v));
	recur(0,N-1); answer(v);
}