#include "monster.h"
#include <bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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);
    for(int i = 1; i < N; i++) {
        qr(a[i], a[i - 1]);
    }
    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) {
        int val;
        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());
        val = y[0].second;
        if(y[1].first == 1 && qr(y[1].second, y[0].second)) {
            val = y[1].second;
        }
        if((int)y.size() > 2 && y[2].first == 1) {
            if(qr(a[i - 1], y[0].second)) {
                val = y[0].second;
            } else if(qr(a[i - 1], y[1].second)) {
                val = y[1].second;
            } else {
                val = y[2].second;
            }
        }
        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;
}