#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
using un = int;
using vuc = vector<un>;
using vol = vector<bool>;
#define REP(i, a, b) for (un i = (un)a ; i < (un)b; i++)
#define FEAC(i, a) for (auto&& i : a)
#define vec vector
#define ALL(x) (x).begin(), (x).end()
std::map<pair<un, un>, bool> cache;
std::mt19937 seed(3589037);
bool first_wins(un a, un b){
if (cache.find({a, b}) != cache.end()) return cache[{a, b}];
cache[{a, b}] = Query(a, b);
cache[{b, a}] = not cache[{a, b}];
return cache[{a, b}];
}
/*
jaky = true <=> nejvetsi
return the best + drops the best from the input
*/
un spocti_nej(vuc& vstup, bool jaky){
un index = 0;
REP(i, 1, vstup.size()){
if (first_wins(vstup[index], vstup[i]) != jaky) index = i;
}
un ret = vstup[index];
swap(vstup[index], vstup.back());
vstup.pop_back();
return ret;
}
vuc serad(vuc vstup, un dole, un nahore){
un N = vstup.size();
shuffle(ALL(vstup), seed);
if (N == 1) return vstup;
if (N == 2){
if (not first_wins(vstup[0], vstup[1])) reverse(ALL(vstup));
return vstup;
}
if (N == 3){
if (dole != -1){
un nejmensi;
REP(i, 0, 3){
if (first_wins(dole, vstup[i])){
nejmensi = i;
break;
}
}
un stredni;
un nejvetsi;
REP(i, 0, 3){
if (nejmensi == i) continue;
if (not first_wins(vstup[nejmensi], vstup[i])){
nejvetsi = i;
stredni = 3 - nejmensi - nejvetsi;
break;
}
else{
stredni = i;
nejvetsi = 3 - nejmensi - stredni;
break;
}
}
return {vstup[nejmensi], vstup[stredni], vstup[nejvetsi]};
}
if (nahore != -1){
un nejvetsi;
REP(i, 0, 3){
if (first_wins(vstup[i], nahore)){
nejvetsi = i;
break;
}
}
un stredni;
un nejmensi;
REP(i, 0, 3){
if (nejvetsi == i) continue;
if (not first_wins(vstup[i], vstup[nejvetsi])){
nejmensi = i;
stredni = 3 - nejmensi - nejvetsi;
break;
}
else{
stredni = i;
nejmensi = 3 - nejvetsi - stredni;
break;
}
}
return {vstup[nejmensi], vstup[stredni], vstup[nejvetsi]};
}
}
if (N == 4){
vuc wins(4, 0);
REP(i, 0, 4) REP(j, i+1, 4) {
if (first_wins(vstup[i], vstup[j])) wins[i]++;
else wins[j]++;
}
vuc male;
vuc velke;
REP(i, 0, 4){
if (wins[i] == 1) male.push_back(vstup[i]);
else if (wins[i] == 2) velke.push_back(vstup[i]);
}
vuc predek = serad(male, -1, -1);
vuc zadek = serad(velke, -1, -1);
return {predek[0], predek[1], zadek[0], zadek[1]};
}
while(true) {
vuc prvky = vstup;
shuffle(ALL(prvky), seed);
un pivot = prvky.back(); prvky.pop_back();
if (dole != -1) {
if (first_wins(dole, pivot)) continue;
}
if (nahore != -1) {
if (first_wins(pivot, nahore)) continue;
}
vuc L, R;
FEAC(p, prvky){
if (not first_wins(p, pivot)) L.push_back(p);
else R.push_back(p);
}
if ((L.size() == 1) or (R.size() == 1)) continue;
shuffle(ALL(L), seed);
shuffle(ALL(R), seed);
un L_max = spocti_nej(L, true);
un R_min = spocti_nej(R, false);
vuc L_res = serad(L, dole, R_min);
vuc R_res = serad(R, L_max, nahore);
vuc res;
res.insert(res.end(), ALL(L_res));
res.push_back(R_min);
res.push_back(pivot);
res.push_back(L_max);
res.insert(res.end(), ALL(R_res));
return res;
}
}
std::vector<int> Solve(int N) {
cache.clear();
vuc vstup(N);
iota(ALL(vstup), 0);
shuffle(ALL(vstup), seed);
vuc vystup = serad(vstup, -1, -1);
vuc ret(N);
REP(i, 0, N) ret[vystup[i]] = i;
return ret;
}
