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

using namespace std;
typedef long long ll;

int cnt[1040];

void 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];
        }
    }
    for(int i = 0; i < n; i++) {
        p[i] = i;
    }
    sort(p.begin(), p.end(), [](int i, int j) {
        return cnt[i] < cnt[j];
    });
    for(int i = 0; i < n - 1; i++) {
        if(cnt[p[i]] == cnt[p[i + 1]]) {
            bool fg = 0;
            for(int j = i + 2; j < n; j++) {
                fg |= a[p[i]][p[j]];
            }
            for(int j = 0; j < i; j++) {
                fg |= a[p[j]][p[i + 1]];
            }
            if(fg) {
                swap(p[i], p[i + 1]);
            }
        }
    }
    vector<int> ans(n);
    for(int i = 0; i < n; i++) {
        ans[i] = v[p[i]];
    }
    ans.swap(v);
}

bool us[1040];

int fnd(vector<int> v) {
    if((int)v.size() <= 30) {
        srt(v);
        return v[0];
    }
    int n = (int)v.size(), m = n;
    vector<int> tt = v;
    while(v.size() > 2  ) {
        vector<int> nw;
        for(int x : v) {
            us[x] = 1;
        }
        for(int l = 0; l < n; l += 4) {
            int r = min(n - 1, l + 3);
            vector<int> d;
            for(int i = l; i <= r; i++) {
                d.push_back(v[i]);
            }
            for(int x : tt) {
                if(d.size() >= 4) break;
                if(!us[x]) {
                    d.push_back(x);
                }
            }
            srt(d);
            nw.push_back(d[0]);
            nw.push_back(d[1]);
        }
        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();
    }
    if(!Query(v[0], v[1])) {
        swap(v[0], v[1]);
    }
    return v[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(!a[p0][pn] && !a[p0][pm]) {
        ans[p0]--;
    }
    else {
        ans[p1]--;
    }

    if(a[pn][p0] && a[pn][p1]) {
        ans[pn]++;
    }
    else {
        ans[pm]++;
    }
    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(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 <= 4) {
       return stupid(n);
   }
   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 && 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;
}