#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 1e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
int n, a[N];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
temp = (temp + (r - l + 1)) % (r - l + 1);
return temp + l;
}
vector<int> er(vector<int> a, int x){
vector<int> b;
for(auto it : a) if(it != x) b.pb(it);
return b;
}
int deg[N];
map<ii, bool> mp;
void solve_brute(vector<int> x, int l, int r){
assert(x.size() == (r - l + 1));
if(x.size() == 1){
a[x[0]] = l;
return;
}
assert(x.size() != 3);
for(int i = 0; i < x.size(); i++){
for(int j = i + 1; j < x.size(); j++){
mp[{x[i], x[j]}] = Query(x[i], x[j]);
if(mp[{x[i], x[j]}]) deg[x[i]]++;
else deg[x[j]]++;
}
}
if(x.size() == 2){
if(!mp[{x[0], x[1]}]){
a[x[0]] = r, a[x[1]] = l;
}
else{
a[x[1]] = r, a[x[0]] = l;
}
return;
}
int mn0 = -1, mn1, mx0 = -1, mx1;
for(auto it : x){
if(deg[it] >= 2 && deg[it] <= x.size() - 3){
a[it] = l + deg[it];
}
if(deg[it] == 1){
if(mn0 == -1) mn0 = it;
else mn1 = it;
}
if(deg[it] == x.size() - 2){
if(mx0 == -1) mx0 = it;
else mx1 = it;
}
}
if(mp[{mn0, mn1}]){
a[mn0] = l; a[mn1] = l + 1;
}
else{
a[mn0] = l + 1; a[mn1] = l;
}
if(mp[{mx0, mx1}]){
a[mx0] = r - 1; a[mx1] = r;
}
else{
a[mx0] = r; a[mx1] = r - 1;
}
}
void solve(vector<int> x, int l, int r){
if(x.size() <= 16){
solve_brute(x, l, r);
return;
}
int temp;
vector<int> vc1, vc2;
while(1){
temp = x[rnd(0, x.size() - 1)];
vc1.clear(), vc2.clear();
for(auto it : x){
if(it == temp) continue;
if(!Query(it, temp)) vc1.pb(it);
else vc2.pb(it);
}
assert(vc1.size() && vc2.size());
if(vc1.size() >= 5 && vc2.size() >= 5) break;
}
//cout << temp << " " << l + vc1.size() << "\n";
a[temp] = l + vc1.size();
int w1 = vc1[0], w2 = vc2[0];
for(auto it : vc1){
if(it == w1) continue;
if(Query(it, w1)) w1 = it;
}
for(auto it : vc2){
if(it == w2) continue;
if(Query(w2, it)) w2 = it;
}
bool ck1 = 0, ck2 = 0;
a[w1] = l + vc1.size() + 1;
a[w2] = l + vc1.size() - 1;
vc1 = er(vc1, w1);
vc2 = er(vc2, w2);
solve(vc1, l, l + vc1.size() - 1);
solve(vc2, r - vc2.size() + 1, r);
}
vector<int> Solve(int _n){
n = _n;
vector<int> temp;
for(int i = 0; i < n; i++) temp.pb(i);
solve(temp, 0, n - 1);
//solve_brute(temp, 0, n - 1);
vector<int> temp2;
for(int i = 0; i < n; i++) temp2.pb(a[i]);
return temp2;
}
/*
void process(){
}
signed main(){
ios_base::sync_with_stdio(0);
process();
}
*/
