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

using namespace std;
typedef long long ll;

int ans[1050][1050];
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));
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            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];
        }
    }
    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) {
    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 += 5) {
            int r = min(n - 1, l + 4);
            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() >= 5) 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();
    }
    vector<int> t;
    for(int x : v) {
        int cc = 0;
        if(x == v.back()) {
            if(t.size() == 2) continue;
            if(t.size() == 0) {
                t.push_back(x);
                continue;
            }
        }
        for(int i = 0; i < m; i++) {
            if(x != i) {
                cc += ask(x, i);
                if(cc > 1) break;
            }
        }
        if(cc <= 1) t.push_back(x);
    }
    if(t.size() == 2 && !ask(t[0], t[1])) {
        swap(t[0], t[1]);
    }
    return t[0];
}

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 = 0; i < n; i++) {
        ans[i] = i;
    }
    int p0 = fnd(ans), pos = 0;
    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);
    }
    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;
}