#include "monster.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
vector<vector<int>> QQ;
bool query(int a, int b){
if(a > b){
if(QQ[b][a] == -1) QQ[b][a] = Query(b, a);
return !QQ[b][a];
}
else{
if(QQ[a][b] == -1) QQ[a][b] = Query(a, b);
return QQ[a][b];
}
}
template<typename it>
void merge_sort(it a, it b){
int n = b-a;
if(n == 1) return;
merge_sort(a, a+n/2);
merge_sort(a+n/2, b);
int* ab = new int[n];
merge(a, a+n/2, a+n/2, b, ab, [&](int x, int y){
return query(y, x);
});
for(int i = 0; i < n; i++) *(a+i) = *(ab+i);
}
vector<int> Solve(int n){
QQ = vector<vector<int>>(n, vector<int>(n, -1));
vector<int> sth(n);
for(int i = 0; i < n; i++) sth[i] = i;
random_shuffle(sth.begin(), sth.end());
merge_sort(sth.begin(), sth.end());
auto win = [=](int x){
vector<int> rt;
for(int i = 0; i < n; i++) if(i != x && query(x, i)) rt.pb(i);
return rt;
};
int z = -1, k = min(n, 10);
vector<int> cnt(k, 0), ss(k);
for(int i = 0; i < k; i++) ss[i] = i;
for(int i = 0; i < k; i++){
for(int j = 0; j < k; j++) if(i != j) cnt[i]+=query(sth[i], sth[j]);
}
sort(ss.begin(), ss.end(), [&](int x, int y){
return cnt[x] < cnt[y];
});
if(query(sth[ss[0]], sth[ss[1]])) z = ss[0];
else z = ss[1];
reverse(sth.begin(), sth.begin()+z+1);
for(;z+1 < n; z++){
for(int i = z+1; i < n; i++) if(query(sth[z], sth[i])){
reverse(sth.begin()+z+1, sth.begin()+i+1);
z = i;
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[sth[i]] = i;
return ans;
}
