#include <bits/stdc++.h>
#include "monster.h"
std::map<std::pair<int, int>, bool> ret;
bool ask(int x, int y) {
if (ret.count({x, y})) return ret[{x, y}];
if (ret.count({y, x})) return !ret[{y, x}];
ret[{x, y}] = Query(x, y);
return ret[{x, y}];
}
std::mt19937 rng(234234);
std::vector<int> Solve(int n) {
ret.clear();
std::vector<int> vec(n);
std::iota(vec.begin(), vec.end(), 0);
std::shuffle(vec.begin(), vec.end(), rng);
std::sort(vec.begin(), vec.end(), [&](int x, int y) {
return ask(y, x);
});
std::vector<std::pair<int, int>> ss;
const int SZ = std::min(n, 8);
for (int i = 0; i < SZ; ++i) {
int cnt = 0;
for (int j = 0; j < SZ; ++j) {
if (i != j) cnt += ask(vec[i], vec[j]);
}
ss.emplace_back(cnt, vec[i]);
}
std::sort(ss.begin(), ss.end());
int mn;
if (ss[0].first == ss[1].first) {
mn = ask(ss[0].second, ss[1].second) ? ss[0].second : ss[1].second;
} else {
mn = ss[0].second;
}
int i = 0, j = std::find(vec.begin(), vec.end(), mn) - vec.begin();
if (j == SZ - 1) {
while (j + 1 < n && ask(vec[1], vec[j + 1])) ++j;
}
std::reverse(vec.begin(), vec.begin() + j + 1);
while (j != n - 1) {
int k = j + 1;
while (ask(vec[k], vec[j])) ++k;
std::reverse(vec.begin() + j + 1, vec.begin() + k + 1);
i = j + 1, j = k;
}
std::vector<int> ans(n);
for (int i = 0; i < n; ++i) ans[vec[i]] = i;
return ans;
}
// int main() {
// int n = s.size();
// for (auto x : Solve(n)) std::cout << x << ' ';
// }
