#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define pb push_back
bool cmp(int a, int b)
{
return Query(a, b);
}
vector<int> tryMerge(int l, int r)
{
if (r - l == 1)
return {l};
int m = (l + r) >> 1;
vector<int> v1 = tryMerge(l, m);
vector<int> v2 = tryMerge(m, r);
int u1 = 0, u2 = 0;
vector<int> ans;
while (u1 < v1.size() or u2 < v2.size())
{
if (u1 == v1.size())
ans.pb(v2[u2++]);
else if (u2 == v2.size())
ans.pb(v1[u1++]);
else
{
if (cmp(v1[u1], v2[u2]))
ans.pb(v2[u2++]);
else
ans.pb(v1[u1++]);
}
}
return ans;
}
std::vector<int> Solve(int N)
{
int n = N;
vector<int> cur = tryMerge(0, n);
int p, pr = -1;
for (p = n - 1; p > 0; --p)
{
pr = p;
{
p--;
while (p - 1 >= 0 and cmp(cur[p - 1], cur[pr]))
p--;
// check if on q[cur[p - 1]] == q[pr] - 1
int bor = p;
if (p + 2 < pr)
{
if (!cmp(cur[p], cur[p + 2]))
bor = p + 1;
}
else if (pr + 1 < n)
{
if (!cmp(cur[p], cur[pr + 1]))
{
bor = p + 1;
}
}
else
{
// is on cur[p] == 99
int cnt1 = 1, cnt2 = 0;
for (int i = 0; i < pr - 1; ++i)
{
cnt1 += cmp(cur[pr], cur[i]);
cnt2 += cmp(cur[pr - 1], cur[i]);
}
if (cnt1 != n - 2)
bor = p;
else
{
if (cnt2 != n - 2)
{
pr--;
}
else
{
bor = pr - 1;
}
}
}
reverse(cur.begin() + bor, cur.begin() + pr + 1);
}
}
vector<int> ans(n);
{
int p = 0;
for (int el : cur)
{
ans[el] = p++;
}
}
return ans;
}
