#include <bits/stdc++.h>
#include "monster.h"
std::vector<int> Solve(int n) {
std::vector<int> vec(n);
std::iota(vec.begin(), vec.end(), 0);
auto dc = [&](auto dc, std::vector<int> vec) -> std::vector<int> {
if (vec.size() <= 1) return vec;
int m = vec.size() / 2;
std::vector<int> lft(vec.begin(), vec.begin() + m), rgt(vec.begin() + m, vec.end());
lft = dc(dc, lft), rgt = dc(dc, rgt);
std::vector<int> ret(vec.size());
std::merge(lft.begin(), lft.end(), rgt.begin(), rgt.end(), ret.begin(), [&](int x, int y) {return Query(y, x);});
return ret;
};
vec = dc(dc, vec);
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;
}
