#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
int do_cnt = 0;
int cnt = 0;
vector<vector<int>> QQ;
vector<vector<int>> extra;
bool query(int a, int b){
if(a > b){
extra[b][a] = 0;
if(QQ[b][a] == -1) QQ[b][a] = Query(b, a), cnt+=do_cnt;
return !QQ[b][a];
}
else{
extra[a][b] = 0;
if(QQ[a][b] == -1) QQ[a][b] = Query(a, b), cnt+=do_cnt;
return QQ[a][b];
}
}
bool query0(int a, int b){
if(a > b){
if(extra[b][a] == -1) extra[b][a] = 1;
if(QQ[b][a] == -1) QQ[b][a] = Query(b, a), cnt+=do_cnt;
return !QQ[b][a];
}
else{
if(extra[a][b] == -1) extra[a][b] = 1;
if(QQ[a][b] == -1) QQ[a][b] = Query(a, b), cnt+=do_cnt;
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));
extra = QQ;
vector<int> sth(n);
for(int i = 0; i < n; i++) sth[i] = i;
do_cnt = 1;
merge_sort(sth.begin(), sth.end());
int cnt2 = 0;
auto win = [&](int x){
vector<int> rt;
for(int i = 0; i < n; i++) if(i != x && query0(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;
bool bl = 0;
for(int j = i+2; j < n0; j++){
if(query(sth[j], sth[i])){
if((i == 0 && win(sth[j-1]).size() != 1) ||
(i != 0 && !query(sth[i-1], sth[j-1])))
reverse(sth.begin()+i, sth.begin()+j-1);
else reverse(sth.begin()+i, sth.begin()+j);
i = j-1;
bl = 1;
break;
}
}
if(!bl){
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;
}
}
if(cnt > 11000) exit(-1);
vector<int> ans(n);
for(int i = 0; i < n; i++) ans[sth[i]] = i;
return ans;
}
