#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
static vector<vector<int>> table;
static int n;
bool query(int a, int b) {
if(table[a][b] != -1) return table[a][b];
bool res = Query(a, b);
table[a][b] = res ? 1 : 0;
table[b][a] = res ? 0 : 1;
return res;
}
bool test(int a, int b) {
bool res = query(a, b);
int cnta = 0, cntb = 0;
for(int i = 0; i < n; ++i) {
if(i != a && query(a, i)) cnta++;
if(i != b && query(b, i)) cntb++;
}
if(cnta == cntb)
return !res;
if(!res && cnta == cntb+1)
return !res;
if(res && cnta+1 == cntb)
return !res;
return res;
// static int arr[] = {3, 1, 4, 2, 0};
// return arr[a] > arr[b];
}
void merge_sort(int l, int r, vector<int> &arr, vector<int> &buf) {
if(r - l <= 1) return;
int mid = (l + r) >> 1;
merge_sort(l, mid, arr, buf);
merge_sort(mid, r, arr, buf);
int i, j, idx = l;
for(i = l, j = mid; i < mid; ++i) {
while(j < r && test(arr[i], arr[j])) {
buf[idx++] = arr[j++];
}
buf[idx++] = arr[i];
}
while(j < r) buf[idx++] = arr[j++];
for(idx = l; idx < r; ++idx)
arr[idx] = buf[idx];
}
vector<int> Solve(int N) {
vector<int> arr(N), buf(N);
table.resize(N); n = N;
for(int i = 0; i < N; ++i)
table[i].assign(N, -1);
for(int i = 0; i < N; ++i)
arr[i] = i;
merge_sort(0, N, arr, buf);
vector<int> ret(N);
for(int i = 0; i < N; ++i)
ret[arr[i]] = i;
return ret;
}
#ifdef local
int main() {
auto ans = Solve(5);
for(int i = 0; i < 5; ++i) {
printf("%d%c", ans[i], " \n"[i == 4]);
}
return 0;
}
#endif
