#include <bits/stdc++.h>
#include "monster.h"
// std::vector<int> s = {4, 2, 1, 0, 3, 5};
// bool Query(int a, int b) {
// if (std::abs(s[a] - s[b]) == 1) {
// return s[a] < s[b];
// }
// return s[a] > s[b];
// }
std::vector<int> Solve(int n) {
std::vector<int> vec(n);
std::iota(vec.begin(), vec.end(), 0);
std::stable_sort(vec.begin(), vec.end(), [&](int x, int y) {
return Query(y, x);
});
for (int i = 0; i + 1 < n; ++i) {
assert(Query(vec[i + 1], vec[i]));
}
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 += Query(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 = Query(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 && Query(vec[1], vec[j + 1])) ++j;
}
std::reverse(vec.begin(), vec.begin() + j + 1);
while (j != n - 1) {
int k = j + 1;
while (Query(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 << ' ';
// }
