#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;
#ifdef LOCAL
#define debug(v) for(auto x: v) cerr << x << " "; cerr << #v << "\n";
#endif
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;
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 n0 = n;
for(int i = 0; i < n0-1; i++){
if(i == 0){
auto s0 = win(sth[0]);
if(s0.size() == 1){
auto s1 = win(s0[0]);
if(s1.size() == 1){
continue;
}
}
}
if(i != 0 && query(sth[i-1], sth[i])) continue;
int a = i+2, b = n0-1;
while(a < b){
int md = (a+b)/2;
if(query(sth[md], sth[i])) b = md;
else{
if(md == a) a = md+1;
else{
if(query(sth[md-1], sth[i])) b = md-1;
else a = md+1;
}
}
}
if(i+2 >= n0 || query(sth[i], sth[a])){
if((i == 0 && win(sth[n0-1]).size() != 1) ||
(i != 0 && !query(sth[i-1], sth[n0-1])))
reverse(sth.begin()+i, sth.begin()+n0-1);
else reverse(sth.begin()+i, sth.begin()+n0);
i = n0;
}
else{
if((i == 0 && win(sth[a-1]).size() != 1) ||
(i != 0 && !query(sth[i-1], sth[a-1])))
reverse(sth.begin()+i, sth.begin()+a-1);
else reverse(sth.begin()+i, sth.begin()+a);
i = a-1;
}
}
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[sth[i]] = i;
return ans;
}
