#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
int n;
namespace sub1{
vector<int>solve(){
vector<int>ans(n, 0);
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
ans[Query(i, j) ? i : j]++;
}
}
for(int i = 0, small = -1, large = -1; i < n; i++){
if(ans[i] == 1){
if(small == -1){
small = i;
}
else{
ans[i] = 1 ^ (ans[small] = (Query(small, i) ? 0 : 1));
}
}
else if(ans[i] == n - 2){
if(large == -1){
large = i;
}
else{
ans[i] = (n - 2) ^ (n - 1) ^ (ans[large] = (Query(large, i) ? n - 2 : n - 1));
}
}
}
return ans;
}
}
namespace sub23{
const int lim = 1e3 + 5;
int cache[lim][lim];
bool ask(int i, int j){
bool z = i > j;
if(z){
swap(i, j);
}
int& ans = cache[i][j];
if(ans != -1){
return ans ^ z;
}
return (ans = Query(i, j)) ^ z;
}
vector<int>p;
int find_zero(){
vector<pair<int, int>>cnt(min(n, 8), make_pair(0, 0));
for(int i = 0; i < min(n, 8); i++){
for(int j = i + 1; j < min(n, 8); j++){
cnt[ask(p[i], p[j]) ? i : j].first++;
}
cnt[i].second = p[i];
}
sort(cnt.begin(), cnt.end());
return cnt[ask(cnt[1].second, cnt[0].second)].second;
}
vector<int>merge_sort(vector<int>p){
if(p.size() < 2){
return p;
}
int m = int(p.size()) >> 1;
vector<int>a = merge_sort(vector<int>(p.begin(), p.begin() + m)), b = merge_sort(vector<int>(p.begin() + m, p.end())), ans(p.size());
merge(a.begin(), a.end(), b.begin(), b.end(), ans.begin(), [&] (int i, int j){
return !ask(i, j);
});
return ans;
}
vector<int>solve(){
memset(cache, -1, sizeof(cache));
p.resize(n);
iota(p.begin(), p.end(), 0);
p = merge_sort(p);
vector<int>cur, ans(1, find_zero());
for(int i = 0; i < n; i++){
if(p[i] != ans[0]){
cur.push_back(p[i]);
if(ask(ans.back(), p[i])){
while(!cur.empty()){
ans.push_back(cur.back());
cur.pop_back();
}
}
}
}
while(!cur.empty()){
ans.push_back(cur.back());
cur.pop_back();
}
vector<int>ret(n);
for(int i = 0; i < n; i++){
ret[ans[i]] = i;
}
return ret;
}
}
vector<int>Solve(int _n){
if((n = _n) <= 200){
return sub1::solve();
}
return sub23::solve();
}
