#include "monster.h"
#include<bits/stdc++.h>
using namespace std;
namespace {
#define vec vector
#define arr array
#define pb push_back
void quick_sort(vec<int>& v, int l0, int r0, int ri = -1) {
if(v.size() == 0) return;
vec<int> left(0);
vec<int> right(0);
bool nr = ri==-1;
if(ri == -1) {
ri = rand()%v.size();
ri = v[ri];
}
for(int i = 0; i<v.size(); i++) {
if(v[i]==ri) continue;
if(Query(ri, v[i])) {
left.pb(v[i]);
}
else {
right.pb(v[i]);
}
}
pair<int, int> nxtl;
pair<int, int> nxtr;
int si = -1;
bool sn = false;
if(left.size() < l0) {
int ll0 = left.size();
nxtl = {ll0, 0};
int lr0 = l0-(left.size()+1);
nxtr = {lr0, r0};
}
else if(right.size() < r0) {
int rr0 = right.size();
nxtr = {0, rr0};
int rl0 = r0-(right.size()+1);
nxtl = {l0, rl0};
}
else if(v.size()-l0-r0 == 2) {
if(left.size() > l0) {
assert(left.size() == l0+1);
nxtl = {l0, 1};
nxtr = {0, r0};
si = -2;
}
else {
assert(right.size() == r0+1);
nxtl = {l0, 0};
nxtr = {1, r0};
si = 2;
}
}
else if(left.size() == l0) {
assert(right.size() == r0);
nxtl = {l0, 0};
nxtr = {0, r0};
}
else if(nr && left.size() == l0+1) {
quick_sort(v, l0, r0, left.back());
return;
}
else if(nr && right.size() == r0+1) {
quick_sort(v, l0, r0, right.front());
return;
}
else {
nxtl = {l0, 1};
nxtr = {1, r0};
sn = true;
}
int lftsz = left.size()-(nxtl.first+nxtl.second);
int rightsz = right.size()-(nxtr.first+nxtr.second);
if(lftsz==3 || lftsz==4 || rightsz==3 || rightsz == 4) {
quick_sort(v, l0, r0);
return;
}
quick_sort(left, nxtl.first, nxtl.second);
quick_sort(right, nxtr.first, nxtr.second);
if(si == -2) {
swap(left[left.size()-1], ri);
}
else if(si == 2) {
swap(right[0], ri);
}
if(sn) {
swap(right[0], left[left.size()-1]);
}
vec<int> res = left;
res.pb(ri);
for(int i = 0; i<right.size(); i++) res.pb(right[i]);
// cerr << "RES-------------" << '\n';
// for(int i = 0; i<res.size(); i++) cerr << res[i] << ' ';
// cerr << '\n';
v = res;
}
}
std::vector<int> Solve(int n) {
std::vector<int> v(n);
for (int i = 0; i < n; i++) v[i] = i;
quick_sort(v, 0, 0);
std::vector<int> res(n);
for(int i = 0; i<n; i++) {
res[v[i]] = i;
}
return res;
}
