#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) {
    if((int)x.size() == 1) return x;
    if(x.empty()) return x;
    int mid = (int)x.size() / 2;
    vector<int> l, r;
    for(int i = 0; i < (int)x.size(); i++) {
        if(i < mid) {
            l.push_back(x[i]);
        } else {
            r.push_back(x[i]);
        }
    }
    x.clear();
    l = sor(l);
    r = sor(r);
    int _l = 0, _r = 0;
    int L = (int)l.size(), R = (int)r.size();
    while(_l < L || _r < R) {
        if(_l == L) {
            x.push_back(r[_r]);
            _r++;
        } else if(_r == R) {
            x.push_back(l[_l]);
            _l++;
        } else {
            if(qr(l[_l], r[_r])) {
                x.push_back(r[_r]);
                _r++;
            } else {
                x.push_back(l[_l]);
                _l++;
            }
        }
    }
    return x;
}
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, 10); i += 2) {
        qr(a[i], a[i - 1]);
    }
    shuffle(a.begin(), a.end(), rng);
    a = sor(a);
    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;
}