#include "monster.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 100 , inf = 1e9 + 10 , mod = 1e9 + 7 ;
int n , X[maxn] , p[maxn] , P[maxn] ;
map <int,int> mp[maxn] ;
int query(int a, int b){
if(mp[a][b] == 0){
mp[a][b] = Query(a,b)+1;
mp[b][a] = 3 - mp[a][b] ;
return mp[a][b]-1 ;
}
return mp[a][b]-1 ;
}
vector <int> mrg(int l, int r){
vector <int> v , vl , vr ;
if(l ==r){
v.pb(P[l]);
return v;
}
int mid = (l+r)/2 ;
vl = mrg(l , mid) ;
vr = mrg(mid+1,r);
int i0 = 0, i1 = 0 ;
while(i0 < sz(vl) && i1 < sz(vr)){
if(query(vl[i0] , vr[i1])){
v.pb(vr[i1]);i1++;
}else{
v.pb(vl[i0]);i0++;
}
}
while(i0 < sz(vl)){
v.pb(vl[i0]);i0++;
}
while(i1 < sz(vr)){
v.pb(vr[i1]) ; i1++;
}
return v;
}
std::vector<int> Solve(int N) {
n = N ;
rep(i , 0 ,n-1)P[i] = i;
shuffle(P , P+n , rng) ;
vector <int>v ;
v = mrg(0 ,n-1);
int ted =0 ;
rep(i ,0 , n-1){
if(i == v[0])continue ;
if(query(v[0] , i)==1)ted++;
}
int fi ;
if(ted == 1){
fi =1 ;
int t =0 ;
rep(i , 0 ,n-1){
if(i==v[1])continue ;
if(query(v[1] , i) == 1)t++ ;
}
if(t==1){
fi =2 ;
}
}else if(ted == n-2){
if(query(v[1] , v.back()) )fi = n ;
else fi = n-1 ;
}else{
fi = ted+1 ;
}
int id =0 ;
rep(i , 0 ,fi-1){
p[i] = fi-i ;
}
int ls= fi-1 , x = fi , ls2 =0 ;
rep(i , fi , n-1){
if(query(v[ls2] , v[i]) == 1){
per(j ,i ,ls+1){
x++;
p[j] = x ;
ls2 = j ;
}
ls = i ;
}
}
vector <int> ans ;
rep(i , 0 ,n-1){
X[v[i]] = p[i] ;
}
rep(i , 0,n-1)ans.pb(X[i]-1);
return ans ;
}
