#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define st first
#define nd second
#define pb push_back
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(a) a.begin(), a.end()
vector<int> T;
int n;
void mergesort(int l, int r) {
if (l == r) return ;
int sr = (l + r)/2;
mergesort(l, sr);
mergesort(sr + 1, r);
vector<int> A;
vector<int> B;
for (int i = l; i <= sr; i++) A.pb(T[i]);
for (int i = sr + 1; i <= r; i++) B.pb(T[i]);
int ita = 0;
int itb = 0;
int sza = A.size();
int szb = B.size();
int it = l;
while (ita < sza || itb < szb) {
if (ita == sza) {
T[it] = B[itb];
itb++;
}
else if (itb == szb) {
T[it] = A[ita];
ita++;
}
else {
if (Query(A[ita], B[itb])) {
T[it] = B[itb];
itb++;
}
else {
T[it] = A[ita];
ita++;
}
}
it++;
}
}
std::vector<int> Solve(int N) {
n = N;
rep(i, n) T.pb(i);
mergesort(0, n - 1);
rep(i, n) {
cout << T[i] << " ";
}
cout << '\n';
int it = 0;
while (it < n) {
if (it > 0) {
if (Query(T[it - 1], T[it])) {
it++;
continue;
}
}
else if (it == 0) {
int cnt = 0;
int kt = -1;
for (int a = 1; a < n; a++) {
if (Query(T[it], T[a])) {
// cout << "a = " << a << endl;
// cout << "T[a] = " << T[a] << endl;
cnt++;
kt = a;
}
}
// cout << "cnt = " << cnt << endl;
if (cnt == 1) {
cnt = 0;
// cout << "kt = " << kt << endl;
for (int a = 0; a < n; a++) {
if (a == kt) continue;
if (Query(T[kt], T[a])) cnt++;
}
if (cnt == 1) {
it++;
continue;
}
}
}
int i = it + 2;
int poc = it;
while (i < n && (Query(T[it], T[i]))) {
it++;
i++;
}
it = poc;
vector<int> pom;
for (int x = it; x < i; x++) pom.pb(T[x]);
reverse(all(pom));
for (int x = it; x < i; x++) T[x] = pom[x - it];
it = i;
}
vector<int> ans;
ans.resize(n);
rep(i, n) ans[T[i]] = i;
return ans;
}
