#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
map<pair<int,int>,int> m;
vector<int> r;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int ask(int a,int b){
if(m.find({a,b})!=m.end()){
return m[{a,b}];
}
if(m.find({b,a})!=m.end()){
return m[{b,a}]^1;
}
return m[{a,b}]=Query(r[a],r[b]);
}
vector<int> dc(int l,int r){\
if(r-l==1){
return vector<int>(1,l);
}
int m=(l+r)>>1;
vector<int> a = dc(l,m);
vector<int> b = dc(m,r);
vector<int> c;
int j=0;
int sz=b.size();
for(int i:a){
while(j<sz&&ask(i,b[j])){
c.push_back(b[j]);
j++;
}
c.push_back(i);
}
while(j<sz){
c.push_back(b[j]);
j++;
}
return c;
}
vector<int> Solve(int n1) {
n=n1;
r.resize(n);
iota(r.begin(),r.end(),0);
shuffle(r.begin(),r.end(),rnd);
vector<int> v = dc(0,n);
vector<int> ans(n),t(n);
int cnt=0;
for(int i=0;i<n-1;i++){
cnt+=ask(v[n-1],v[i]);
//cout<<ask(v[n-1],v[i])<<endl;
}
//cout<<cnt<<endl;
int i=n-1;
for(;cnt<n;cnt++,i--){
t[i]=cnt;
}
int last=n-1;
while(i>=0){
int rec=i;
while(!ask(v[i],v[last])){
i--;
}
//cout<<"i:"<<i<<endl;
last=rec;
cnt=rec;
for(int j=i;j<=rec;j++){
t[j]=cnt;
cnt--;
}
i--;
}
for(int i=0;i<n;i++){
ans[r[v[i]]]=t[i];
}
return ans;
}
/*
9
1 5 2 0 8 6 3 4 7
*/
