#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l)==r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
#include "monster.h"
namespace {
const int MAX_N = 1010;
int ans[MAX_N][MAX_N], qcnt;
int qry(int i, int j) {
if (!ans[i][j]) {
++qcnt;
ans[j][i] = ans[i][j] = Query(i, j) ? i + 10 : j + 10;
}
return ans[i][j] - 10;
}
} // namespace
std::vector<int> Solve(int N) {
vector<int> sorted(N); iota(AI(sorted), 0);
{
int bad_cnt = 0;
auto cmp = [&](int i, int j) {
return qry(i, j) == j;
};
vector< vector<int> > ids;
for (int i = 0;i < N;++i) {
ids.pb();
ids.back().pb(i);
while (ids.size() > 1 && end(ids)[-2].size() == end(ids)[-1].size()) {
vector<int> nid ( end(ids)[-2].size() + end(ids)[-1].size() );
merge(AI(end(ids)[-2]), AI(end(ids)[-1]), begin(nid), cmp);
ids.pop_back();
ids.pop_back();
ids.pb(nid);
bad_cnt += nid.size();
}
}
while (ids.size() > 1) {
vector<int> nid ( end(ids)[-2].size() + end(ids)[-1].size() );
merge(AI(end(ids)[-2]), AI(end(ids)[-1]), begin(nid), cmp);
ids.pop_back();
ids.pop_back();
ids.pb(nid);
bad_cnt += nid.size();
}
sorted = ids[0];
}
auto find_max = [&]() {
vector<pair<int,int>> cand;
for (int i : sorted) {
int lose = 0, sz = 0;
for (auto [id, cnt] : cand) {
if (qry(i, id) == i) ++cnt;
else ++lose;
if (cnt <= 1)
cand[sz++] = {id, cnt};
}
cand.resize(sz);
if (lose <= 1) cand.pb(i, lose);
}
DE(cand.size());
assert(cand.size() > 1);
assert(cand.size() <= 3);
if (cand.size() == 3) {
vector<int> big;
for (auto [id, cnt] : cand) {
big.pb(id);
}
vector<int> lft;
{
int x = big[0], y = big[1], z = big[2];
for (int i = N-4;i >= 0;--i) {
if (qry(sorted[i], x) != x) {
lft = {y, z};
break;
}
if (qry(sorted[i], y) != y) {
lft = {x, z};
break;
}
if (qry(sorted[i], z) != z) {
lft = {x, y};
break;
}
}
}
return lft[0] + lft[1] - qry(lft[0], lft[1]);
}
if (cand.size() == 2) {
int a = cand[0].first, b = cand[1].first;
return a + b - qry(a, b);
}
assert(false);
};
auto it = find(AI(sorted), find_max());
swap(*it, sorted.back() );
int lst = sorted.back();
vector<int> stk, rev{lst};
for (int i = N-2;i >= 0;--i) {
stk.pb( sorted[i] );
if (qry( sorted[i], lst ) == sorted[i]) {
while (stk.size()) {
rev.pb(stk.back()); stk.pop_back();
}
lst = rev.back();
}
}
sorted = rev;
reverse(AI(sorted));
vector<int> res(N);
for (int i = 0;i < N;++i)
res[ sorted[i] ] = i;
return res;
}
