#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> sor(vector<int> x) {
//     int mid = (int)x.size() / 2;
//     vector<int> l, r;
//     for(int i = 0; i < (int)x.size(); i++) {
//         if(i < mid) {
//             x.push_back()
//         }
//     }
// }
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 < min(N, 60); i += 2) {
        qr(a[i], a[i - 1]);
    }
    shuffle(a.begin(), a.end(), rng);
    stable_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;
        if(!i) {
            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;
                }
            }
        } else {
            for(int j = i; j < min(N, i + 10); j++) {
                if(qr(a[i - 1], a[j])) {
                    val = a[j];
                    break;
                }
            }
        }
        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;
}