#include "monster.h"
#include<bits/stdc++.h>
using namespace std;

void solve(vector<int> &T, int l, int r) {
    if(l == r) {
        return;
    }
    int mid = l + r >> 1;
    solve(T, l, mid);
    solve(T, mid + 1, r);
    vector<int> T_(r - l + 1);
    for(int i = l, j = l, k = mid + 1; i <= r; i++) {
        if(j > mid || (k <= r && Query(T[j], T[k]))) {
            T_[i - l] = T[k++];
        }
        else {
            T_[i - l] = T[j++];
        }
    }
    for(int i = l; i <= r; i++) {
        T[i] = T_[i - l];
    }
}

vector<int> T(1000), cnt(10);

bool cmp(int x, int y) {
    return cnt[T[x]] < cnt[T[y]];
}

vector<int> Solve(int n) {
    for(int i = 0; i < n; i++) {
        T[i] = i;
    }
    solve(T, 0, n - 1);
    vector<int> id(10);
    for(int i = 0; i < min(n, 10); i++) {
        id[i] = i;
        for(int j = i + 1; j < min(n, 10); j++) {
            if(Query(T[i], T[j])) {
                cnt[T[i]]++;
            }
            else {
                cnt[T[j]]++;
            }
        }
    }
    sort(id.begin(), id.begin() + min(n, 10), cmp);
    vector<int> Ans(n);
    int st = 0, ed = 0, tn = 0;
    if(cnt[T[id[0]]] != cnt[T[id[1]]]) {
        ed = id[0];
    }
    else {
        if(Query(T[id[0]], T[id[1]])) {
            ed = id[0];
        }
        else {
            ed = id[1];
        }
    }
    while(1) {
        for(int i = ed; i >= st; i--) {
            Ans[T[i]] = tn++;
        }
        if(ed == n - 1) {
            break;
        }
        int st_ = ed + 1, ed_ = ed + 1;
        while(Query(T[ed_], T[st])) {
            ed_++;
            assert(ed_ < n);
        }
        st = st_;
        ed = ed_;
    }

    return Ans;
}