#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);
namespace {
bool example_variable;
}
vector<int> ans;
void work(int l, int r) {
if (l == r) return;
int m = (l+r) / 2;
work(l, m);
work(m+1, r);
vector<int> left, right, temp;
for (int i = l; i <= m; i++) left.push_back(ans[i]);
for (int i = m+1; i <= r; i++) right.push_back(ans[i]);
int i = 0, j = 0;
while (i < left.size() and j < right.size()) {
bool smol = Query(left[i], right[j]);
if (!smol) {
temp.push_back(left[i++]);
} else {
temp.push_back(right[j++]);
}
}
while (i < left.size()) {
temp.push_back(left[i++]);
}
while (j < right.size()) {
temp.push_back(right[j++]);
}
assert(temp.size() == (r - l + 1));
for (int i = 0; i < temp.size(); i++) {
ans[i + l] = temp[i];
}
}
void flip(int l, int r) {
reverse(ans.begin() + l, ans.begin() + r + 1);
}
void fix(int N) {
vector<int> cnt(N);
int LN = min(N, int(ceil(log2(N)) + 5));
for (int i = 0; i < LN; i++) {
for (int j = i+1; j < LN; j++) {
bool smol = Query(ans[i], ans[j]);
(smol ? ++cnt[i] : ++cnt[j]);
}
}
int zero = -1;
for (int i = 0; i < LN; i++) {
if (cnt[i] == 0) {
zero = i;
}
}
if (zero == -1) {
int u = -1, v = -1;
for (int i = 0; i < LN; i++) {
if (cnt[i] == 1) {
u = i;
break;
}
}
for (int i = u+1; i < LN; i++) {
if (cnt[i] == 1) {
v = i;
break;
}
}
bool smol = Query(ans[u], ans[v]);
zero = (smol ? u : v);
}
flip(0, zero);
int last = zero;
for (int i = last + 1; i < N; i++) {
bool smol = Query(ans[last], ans[i]);
if (smol) {
flip(last + 1, i);
last = i;
}
}
}
vector<int> Solve(int N) {
ans.resize(N);
iota(all(ans), 0);
work(0, N-1);
// for (auto &x : ans) {
// cerr << x << " ";
// } cerr << endl;
fix(N);
// for (auto &x : ans) {
// cerr << x << " ";
// } cerr << endl;
vector<int> str(N);
for (int i = 0; i < N; i++) {
str[ans[i]] = i;
}
// for (auto &x : str) {
// cerr << x << " ";
// } cerr << endl;
return str;
}
// 5
// 3 1 4 2 0
// 1 0 2 4 3
// 8
// 4 7 3 2 1 5 6 0
// 4 7 0 2 3 1 6 5
// 1 0 4 3 2 7 6 5
// 1 0 5 6 3 2 7 4
// 7 4 5 6 2 3 0 1
// 4 7 2 3 6 5 0 1
// 1 0 3 2 6 5 4 7
// 7 4 3 2 0 5 6 1
