#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(532123);
int mem[1001][1001];
int qr(int x, int y) {
if(mem[x][y] != -1) return mem[x][y];
int k = Query(x, y);
mem[x][y] = k;
mem[y][x] = 1 - k;
return k;
}
vector<int> Solve(int N) {
memset(mem, -1, sizeof(mem));
vector<int> a(N), res(N);
iota(a.begin(), a.end(), 0);
shuffle(a.begin(), a.end(), rng);
sort(a.begin(), a.end(), [&](int x, int y){
return !qr(x, y);
});
int i = 0;
auto calc = [&](vector<int> x, int v) {
int ret = 0;
for(int i : x) if(i != v) {
if(qr(v, i)) {
ret++;
}
}
return ret;
};
while(i < N - 1) {
vector<int> x;
vector<pair<int, int>> y;
for(int j = i; j < min(N, i + 10); j++) {
x.push_back(a[j]);
}
for(int j : x) {
y.emplace_back(calc(x, j), j);
}
sort(y.begin(), y.end());
int val = y[0].second;
if(qr(y[1].second, y[0].second)) {
val = y[1].second;
}
if((int)y.size() > 2 && y[2].first == 1) {
val = a[i + 2];
}
for(int j = i; j < N; j++) {
if(a[j] == val) {
reverse(a.begin() + i, a.begin() + j + 1);
i = j + 1;
break;
}
}
}
for(int i = 0; i < N; i++) {
res[a[i]] = i;
}
return res;
}