#include<bits/stdc++.h>
#define MAXN 1007
#include "monster.h"
using namespace std;
namespace {
bool example_variable;
int n;
} // namespace
int compared[MAXN][MAXN];
int deg[MAXN];
int value[MAXN];
int ask(int x,int y){
if(compared[x][y]!=0)return compared[x][y];
compared[x][y]=1+Query(x,y);
compared[y][x]=3-compared[x][y];
return compared[x][y];
}
bool cmp(int x,int y){
if(deg[x]!=deg[y])return deg[x]<deg[y];
return ask(x,y)==2;
}
bool cmp2(int x,int y){
return value[x]<value[y];
}
void dumb(int l,int r,vector<int> v){
for(int i:v)deg[i]=0;
for(int i=0;i<v.size();i++){
for(int f=i+1;f<v.size();f++){
if(ask(v[i],v[f])==2)deg[v[i]]++;
else deg[v[f]]++;
}
}
sort(v.begin(),v.end(),cmp);
for(int i=0;i<v.size();i++){
value[v[i]]=l+i;
}
}
int biggest(vector<int> v){
int curr=v[0];
for(int i=1;i<v.size();i++){
if(ask(v[i],curr)==2)curr=v[i];
}
return curr;
}
void find_triple(vector<int> v,int &p1,int &p2,int &p3){
p1=v[0]; p2=v[1]; p3=-1;
if(ask(p1,p2)==1)swap(p1,p2);
vector<int> small,big;
for(int i=2;i<v.size();i++){
if(ask(p2,v[i])==2 and ask(v[i],p1)==2){
p3=v[i]; break;
}
if(ask(p2,v[i])==2 and ask(p1,v[i])==2){
small.push_back(v[i]);
}
}
if(p3==-1){
p1=biggest(small);
for(int i=0;i<v.size();i++){
if(v[i]==p1 or v[i]==p2)continue;
if(ask(p1,v[i])==2 and ask(v[i],p2)==2){
p3=v[i]; break;
}
}
}
}
void solve(int l,int r,vector<int> v){
if(v.empty())return;
if(r-l+1<=4){
dumb(l,r,v);
return;
}else{
random_shuffle(v.begin(),v.end());
int p1,p2,p3,p4=-1,pivot;
find_triple(v,p1,p2,p3);
vector<int> ll,rr;
for(int i=0;i<v.size();i++){
if(v[i]==p1 or v[i]==p2 or v[i]==p3)continue;
if(ask(p1,v[i])==1 and ask(p2,v[i])==1 and ask(p3,v[i])==1){
rr.push_back(v[i]); continue;
}
if(ask(p1,v[i])==2 and ask(p2,v[i])==2 and ask(p3,v[i])==2){
ll.push_back(v[i]); continue;
}
if(p4==-1)p4=v[i];
else{
int sum=ask(p1,v[i]) + ask(p2,v[i]) + ask(p3,v[i]);
if(sum==4)rr.push_back(v[i]);
else ll.push_back(v[i]);
}
}
dumb(0,3,{p1,p2,p3,p4});
if(value[p1]>=1 and value[p1]<=2)pivot=p1;
if(value[p2]>=1 and value[p2]<=2)pivot=p2;
if(value[p3]>=1 and value[p3]<=2)pivot=p3;
int sz=l+int(ll.size());
value[p1]+=sz; value[p2]+=sz; value[p3]+=sz; value[p4]+=sz;
vector<int> sp={p1,p2,p3,p4};
sort(sp.begin(),sp.end(),cmp2);
if(!ll.empty()){
int pt=0;
while(ll.size()<4){
ll.push_back(sp[pt]); pt++;
}
solve(l,l+int(ll.size())-1,ll);
}
if(!rr.empty()){
int pt=3;
while(rr.size()<4){
rr.push_back(sp[pt]); pt--;
}
solve(r-int(rr.size())+1,r,rr);
}
}
}
vector<int> Solve(int N){
n=N;
vector<int> v,ans;
for(int i=0;i<n;i++)v.push_back(i);
solve(0,n-1,v);
for(int i=0;i<n;i++){
ans.push_back(value[i]);
}
return ans;
}
