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

using namespace std;
typedef long long ll;

int cnt[1040];

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] = Query(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 += Query(x, i);
                if(cc > 1) break;
            }
        }
        if(cc <= 1) t.push_back(x);
    }
    if(t.size() == 2 && !Query(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(Query(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 && Query(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;
}