#include "monster.h"
#include <bits/stdc++.h>
#define ent '\n'

using namespace std;
typedef long long ll;

int ans[1050][1050];
int pos[1040];
int cnt[1040];

bool ask(int x, int y) {
    if(ans[x][y] != 0) {
        return (ans[x][y] == 1);
    }
    ans[x][y] = 1;
    if(Query(x, y) == 0) ans[x][y] = -1;
    ans[y][x] = -ans[x][y];
    return (ans[x][y] == 1);
}

vector<int> srt(vector<int> &v) {
    int n = (int)v.size();
    vector<int> p(n);
    for(int i = 0; i < n; i++) {
        cnt[i] = 0;
    }
    vector<vector<bool>> a(n, vector<bool> (n, 0));
    auto b = a;
    for(;1;) {
        vector<pair<int, int>> t;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(b[i][j] || cnt[i] > 1 && cnt[j] > 1) continue;
                if(cnt[i] <= cnt[j]) t.push_back({i, j});
                else t.push_back({j, i});
            }
        }
        sort(t.begin(), t.end(), [](pair<int, int> x, pair<int, int> y) {
            return pair<int, int> ({cnt[x.first], cnt[x.second]}) < pair<int, int> ({cnt[y.first], cnt[y.second]});
        });
        if(t.size() == 0) break;
        int i = t[0].first, j = t[0].second;
        a[i][j] = ask(v[i], v[j]);
        a[j][i] = 1 - a[i][j];
        cnt[i] += a[i][j];
        cnt[j] += a[j][i];
        b[i][j] = b[j][i] = 1;
    }
    vector<int> ans;
    for(int i = 0; i < n; i++) {
        if(cnt[i] <= 1) {
            ans.push_back(v[i]);
        }
    }
    return ans;
}

bool us[1040];

int fnd(vector<int> v) {
    vector<int> p = v;
    int n = (int)v.size(), m = n;
    while(v.size() > 3) {
        vector<int> nw;
        for(int x : v) {
            us[x] = 1;
        }
        for(int l = 0; l < n; l += 6) {
            int r = min(n - 1, l + 5);
            vector<int> d;
            for(int i = l; i <= r; i++) {
                d.push_back(v[i]);
            }
            for(int x = 0; x < m; x++) {
                if(d.size() >= 6) break;
                if(!us[x]) {
                    d.push_back(x);
                }
            }
            auto t = srt(d);
            for(int x : t) {
                if(us[x]) nw.push_back(x);
            }
        }
        for(int x : v) {
            us[x] = 0;
        }
        nw.swap(v);
        sort(v.begin(), v.end());
        v.resize(unique(v.begin(), v.end()) - v.begin());
        n = (int)v.size();
    }
    sort(v.begin(), v.end(), [](int x, int y) {
        return pos[x] < pos[y];
    });
    if(v.size() == 3) {
        if(ask(p[0], v[2])) {
            return v[2];
        }
        v.pop_back();
    }
    if(v.size() == 1) return v[0];
    if(v.size() > 2) {
        if(ask(p[0], v[2])) {
            v.erase(v.begin() + 1);
        }
        else v.pop_back();
    }
    if(ask(v[0], v[1])) return v[0];
    return v[1];
}

vector<int> stupid(int n) {
    vector<int> ans(n), pos(n), used(n);
    vector<vector<bool>> a(n, vector<bool> (n, 0));
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            a[i][j] = Query(i, j);
            a[j][i] = 1 - a[i][j];
        }
    }
    int cnt = n, p0 = -1, p1 = -1, pn = -1, pm = -1;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i != j) {
                ans[i] += a[i][j];
            }
        }
        pos[ans[i]] = i;
        if(ans[i] == 1) {
            p1 = i;
            if(p0 < 0) p0 = i;
        }
        if(ans[i] == n - 2) {
            pm = i;
            if(pn < 0) pn = i;
        }
    }
    if(n == 4) {
        if(!a[p0][pn] && !a[p0][pm]) {
            ans[p0]--;
        }
        else {
            ans[p1]--;
        }

        if(a[pn][p0] && a[pn][p1]) {
            ans[pn]++;
        }
        else {
            ans[pm]++;
        }
    }
    else {
        if(a[p0][pos[2]]) {
            ans[p1]--;
        }
        else {
            ans[p0]--;
        }

        if(a[pos[n - 3]][pn]) {
            ans[pm]++;
        }
        else {
            ans[pn]++;
        }
    }
    return ans;
}

vector<int> Solve(int n) {
    vector<int> p = {0}, ans(n);
    for(int i = 1; i < n; i++) {
        int pos = -1;
        for(int l = 0, r = i - 1; l <= r;) {
            int mid = l + r >> 1;
            if(ask(i, p[mid])) {
                l = mid + 1;
                pos = mid;
            }
            else r = mid - 1;
        }
        vector<int> nw;
        for(int i = 0; i <= pos; i++) {
            nw.push_back(p[i]);
        }
        nw.push_back(i);
        for(int i = pos + 1; i < p.size(); i++) {
            nw.push_back(p[i]);
        }
        p.swap(nw);
    }
    if(n <= 100) {
        return stupid(n);
    }
    for(int i = 0; i < n; i++) {
        pos[p[i]] = i;
    }
    int p0 = fnd(p), pos = 0;
    while(p[pos] != p0) {
        pos++;
    }
    reverse(p.begin(), p.begin() + pos + 1);
    for(int i = 0; i + 1 < n;) {
        int j = i + 1;
        while(j < n && ask(p[i], p[j]) == 0) {
            j++;
        }
        reverse(p.begin() + i + 1, p.begin() + j + 1);
        i = j;
    }
    for(int i = 0; i < n; i++) {
        ans[p[i]] = i;
    }
    return ans;
}