#include "monster.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <chrono>
#include <random>
typedef long long llong;
const int MAXN = 1000 + 10;
const int INF = 1e9;
std::mt19937 rng(15); //std::chrono::steady_clock::now().time_since_epoch().count());
std::vector <int> v;
std::vector <int> res;
void rec(int l, int r)
{
if (l == r)
{
return;
}
int mid = (l + r) / 2;
rec(l, mid);
rec(mid + 1, r);
int ptr = l;
int lPtr = l, rPtr = mid + 1;
while (lPtr <= mid || rPtr <= r)
{
if (lPtr == mid + 1)
{
res[ptr++] = v[rPtr++];
continue;
}
if (rPtr == r + 1)
{
res[ptr++] = v[lPtr++];
continue;
}
if (Query(v[rPtr], v[lPtr]))
{
res[ptr++] = v[lPtr++];
} else
{
res[ptr++] = v[rPtr++];
}
}
for (int i = l ; i <= r ; ++i)
{
v[i] = res[i];
}
}
int cnt[10];
std::vector <int> Solve(int n)
{
v.resize(n);
res.resize(n);
std::iota(v.begin(), v.end(), 0);
std::shuffle(v.begin(), v.end(), rng);
rec(0, n - 1);
for (int i = 0 ; i < std::min(10, n) ; ++i)
{
for (int j = i + 1 ; j < std::min(10, n) ; ++j)
{
if (Query(v[i], v[j])) cnt[i]++;
else cnt[j]++;
}
}
int min = -1;
for (int i = 0 ; i < std::min(10, n) ; ++i)
{
if (cnt[i] == 1)
{
if (min == -1 || Query(v[i], v[min])) min = i;
}
}
if (min != 0)
{
int beg = v[0];
int zero = v[min];
v.erase(v.begin() + min);
v.erase(v.begin());
v.insert(v.begin(), zero);
v.insert(v.begin() + min, beg);
}
int idx = 0;
for (int i = 1 ; i < n ; ++i)
{
if (Query(v[idx], v[i]))
{
std::reverse(v.begin() + idx + 1, v.begin() + i + 1);
idx = i;
}
}
for (int i = 0 ; i < n ; ++i)
{
res[v[i]] = i;
}
return res;
}
