#include "inv.h"
#include <bits/stdc++.h>
using namespace std; 
#define mp make_pair
#define pii pair<int,int>
map<pii,int>H;
void init(int c, int t){
	return;
}
int mquery(int l,int r){
    if(l==r)return 0; 
    if(!H.count(mp(l,r))){
        return H[mp(l,r)]=query(l,r);
    }else{
        return H[mp(l,r)];
    }
}
const int N=2026;
int w[N][N],g[N],f[N];
bool compre(int a,int b){
    int c1=mquery(a,b);
    c1^=(w[a][b-1]&1);
    int c2=mquery(a+1,b);
    c2^=(w[a+1][b-1]&1);
    if(c1^c2)return 0;
    else return 1;
}
void upd(int n){
    for(int i=1;i<=n;i++)f[g[i]]=i;
    int cnt=0;
    for(int i=n-1;i>=1;i--){
        cnt+=(f[i]>f[n]);
        w[i][n]=w[i][n-1]+cnt;
    }
    return;
}
vector<int> solve(int n){
    vector<int>ans(n);
    for(int i=1;i<=n+5;i++)f[i]=g[i];
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            w[i][j]=0;
        }
    }
    H.clear();
    for(int i=1,pos;i<=n;i++){
        if(i==1)pos=1;
        else{
            if(!compre(g[1],i)){
                pos=1;
            }else{
                int L=1,R=i-1,mid;
                while(L<R){
                    mid=(L+R+1)>>1;
                    if(compre(g[mid],i))L=mid;
                    else R=mid-1;
                }
                pos=L+1;
            }
        }
        for(int j=i-1;j>=pos;j--){
            g[j+1]=g[j];
        }
        g[pos]=i;
        upd(i);
    }
    for(int i=0;i<n;i++)ans[i]=f[i+1];
	return ans;
}