#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
#define all(a) (a).begin(),(a).end()
#define bg(a) (a).begin()
#define ed(a) (a).end()
#define sz(a) (int)(a).size()
#define ii pair<int,int>
#define fi first
#define se second
vector<int> sort(vector<int> cr){
if(sz(cr)==1) return cr;
int m=sz(cr)/2;
vector<int> a(bg(cr),bg(cr)+m),b(bg(cr)+m,ed(cr));
a=sort(a); b=sort(b);
int ap=0,bp=0;
for(int i=0;i<sz(cr);++i){
if(ap==sz(a)) cr[i]=b[bp++];
else if(bp==sz(b)) cr[i]=a[ap++];
else if(Query(a[ap],b[bp])) cr[i]=b[bp++];
else cr[i]=a[ap++];
}
return cr;
}
vector<int> Solve(int n){
vector<int> ans(n);
iota(all(ans),0);
ans=sort(ans);
vector<ii> win(min(n,10));
for(int i=0;i<min(n,10);++i){
win[i].se=ans[i];
for(int j=i+1;j<min(n,10);++j)
if(Query(ans[i],ans[j])) ++win[i].fi;
else ++win[j].fi;
}
sort(all(win));
int bk=win[0].se;
if(Query(win[1].se,win[0].se)) bk=win[1].se;
ans.erase(find(all(ans),bk));
ans.insert(bg(ans),bk);
for(int i=1;i<n;++i){
int j=i;
for(;j<n&&Query(ans[j],bk);++j);
reverse(bg(ans)+i,bg(ans)+min(j+1,n));
i=j; bk=ans[i];
}
vector<int> out(n);
for(int i=0;i<n;++i) out[ans[i]]=i;
return out;
}
