#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
bool example_variable;
} // namespace
map<pair<int,int>,int>mp;
bool query(int a,int b){
if(mp.count({a,b}))return mp[{a,b}];
mp[{a,b}]=Query(a,b); mp[{b,a}]=(!mp[{a,b}]);
return mp[{a,b}];
}
vector<int>v;
void merge(int l,int r){
if(l==r)return;
int mid=(l+r)/2;
merge(l,mid),merge(mid+1,r);
int posl=l,posr=mid+1;
vector<int>baru;
while(posl<=mid || posr<=r){
if(posl>mid){
baru.push_back(v[posr]);posr++;
}
else if(posr>r){
baru.push_back(v[posl]); posl++;
}
else if(query(v[posl],v[posr])){
baru.push_back(v[posr]); posr++;
}
else{
baru.push_back(v[posl]); posl++;
}
}
// cout<<l<<" k "<<r<<endl;
for(int q=l;q<=r;q++){
v[q]=baru[q-l];
//cout<<baru[q-l]<<' ';
}
// cout<<endl;
}
mt19937 rnd(23203);
int cnt[1002];
int cari(int sz){
vector<int>a;
for(int q=0;q<sz;q++){
for(int w=0;w<sz;w++){
if(q==w)continue;
cnt[q]+=query(v[q],v[w]);
}
if(cnt[q]==1)a.push_back(v[q]);
}
if(a.size()==1)return a[0];
if(query(a[0],a[1]))return a[0];
return a[1];
}
vector<int> Solve(int N) {
for(int q=0;q<N;q++){
v.push_back(q);
}
shuffle(v.begin(),v.end(),rnd);
merge(0,N-1);
int idx=cari(min(N,15));
v.erase(find(v.begin(),v.end(),idx));
v.insert(v.begin(),idx);
// for(auto x:v){
// cout<<x<<' ';
// }
// cout<<endl;
int lst=0;
for(int q=1;q<v.size();q++){
if(query(v[lst],v[q])){
reverse(v.begin()+lst+1,v.begin()+q+1);
lst=q;
}
}
vector<int>ans(N);
for(int q=0;q<v.size();q++){
//cout<<v[q]<<endl;
ans[v[q]]=q;
}
return ans;
}
