#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
namespace {
bool example_variable;
} // namespace
vi solveP(int l, int r) {
if (l == r) return {l};
vi lp = solveP(l,(l+r)/2), rp = solveP(1+(l+r)/2,r);
vi ans;
int p1 = 0, p2 = 0;
while (p1 < lp.size() || p2 < rp.size()) {
if (p1 < lp.size() && p2 < rp.size()) {
if (!Query(lp[p1],rp[p2])) ans.push_back(rp[p2++]);
else ans.push_back(lp[p1++]);
}
else if (p1 < lp.size()) ans.push_back(lp[p1++]);
else ans.push_back(rp[p2++]);
}
return ans;
}
vector<int> badSolve(int N, vi ans) {
map<int,int> v;
for (int i = 0; i<N; ++i) {
for (int j = i+1; j<N; ++j) {
++v[Query(ans[i],ans[j]) ? ans[i] : ans[j]];
}
}
sort(ans.begin(), ans.end(), [&](int a, int b) {return v[a] < v[b];});
if (!Query(ans[0], ans[1])) swap(ans[0], ans[1]);
if (!Query(ans[N-2], ans[N-1])) swap(ans[N-2], ans[N-1]);
return ans;
}
vi Solve(int N) {
vi v = solveP(0,N-1);
reverse(v.begin(), v.end());
int k = min(N, 20);
vi partial(v.begin(), v.begin()+k);
int zero = badSolve(k,partial)[0];
int ind = find(v.begin(), v.end(), zero)-v.begin();
reverse(v.begin(), v.begin()+ind+1);
while (ind < N-1) {
int i = ind+1;
while (Query(v[i],v[ind])) ++i;
reverse(v.begin()+ind+1,v.begin()+i+1);
ind = i;
}
vi ret(N); for (int i = 0; i<N; ++i) ret[v[i]] = i;
return ret;
}
