#include "monster.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define f0r(i,N) for(int i = 0; i < N; i++)
#define FOR(i,k,N) for(int i = k; i < N; i++)
#define dout(x) cout<<x<<' '<<#x<<endl
#define dout2(x,y) cout<<x<<' '<<#x<<' '<<y<<' '<<#y<<endl
#define vout(v) cout<<#v<<": "; for(auto u : v)cout<<u<<' '; cout<<endl
using namespace std;
void dnc(int l, int r, vi &v){
if(l == r)return; int mid = l + r >> 1; vi a, b; for(int i = 0; i <= mid - l; i++)a.pb(v[i]);
FOR(i, mid-l+1, r-l+1)b.pb(v[i]); dnc(l, mid, a); dnc(mid+1, r, b);
int p1 = 0, p2 = 0; vi tmp; while(p1 < a.size() || p2 < b.size()){
if(p1 == a.size())tmp.pb(b[p2]), p2++; else if(p2 == b.size())tmp.pb(a[p1]), p1++; else{
if(!Query(a[p1], b[p2]))tmp.pb(a[p1]), p1++; else tmp.pb(b[p2]), p2++;
}
} v = tmp;
}
std::vector<int> Solve(int N) {
vi v(N); f0r(i,N)v[i] = i; dnc(0, N-1, v); int d = 0; vi res(N); FOR(i,1,N)res[i] = Query(v[0], v[i]), d += res[i];
if(d == 1){
FOR(i,1,N)if(res[i] == 1){
int tmp = 0; f0r(j, N)if(i != j)tmp += Query(v[i], v[j]); if(tmp == 1)d--;
}
}
else if(d == N-2){
FOR(i,1,N)if(res[i] == 0){
int tmp = 0; f0r(j, N)if(i != j)tmp += Query(v[i], v[j]); if(tmp == N-2)d++;
}
}
int pt = d; reverse(v.begin(), v.begin() + pt + 1); while(pt < N-1){
int nxt; FOR(i,pt + 1,N)if(Query(v[pt], v[i])){nxt = i; break;} reverse(v.begin() + pt + 1, v.begin() + nxt + 1); pt = nxt;
} vi ans(N); f0r(i,N)ans[v[i]] = i;
return ans;
}
