#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
namespace da {
int query_count = 0;
}
namespace {
map<pair<int, int>, bool> R;
} // namespace
bool cmp(int st, int dr) {
if(R.count({st, dr})) return R[{st, dr}];
else {
++da::query_count;
R[{dr, st}] = !(R[{st, dr}] = Query(st, dr));
return R[{st, dr}];
}
}
bool is_cand(int p, int n) {
int nr = 0;
for(int i = 0; i < n; ++i)
if(i != p) nr += cmp(p, i);
return nr == 1;
}
using vi = vector<int>;
void mrg_srt(vi &O, vi &tmp, int st, int dr) {
if(st == dr) return;
int mij = (st + dr) >> 1;
mrg_srt(O, tmp, st, mij);
mrg_srt(O, tmp, mij + 1, dr);
int p1 = st, p2 = mij + 1, pf = st;
while(p1 <= mij && p2 <= dr)
tmp[pf++] = cmp(O[p1], O[p2]) ? O[p2++] : O[p1++];
while(p1 <= mij) tmp[pf++] = O[p1++];
while(p2 <= dr) tmp[pf++] = O[p2++];
for(int i = st; i <= dr; ++i) O[i] = tmp[i];
}
vector<int> Solve(int n) {
vector<int> O(n), Tmp(n);
for(int i = 0; i < n; ++i) O[i] = i;
mrg_srt(O, Tmp, 0, n - 1);
//printf("Sort Init: %d\n", da::query_count);
vector<int> OC;
for(int i = 0; i < 3; ++i) if(is_cand(O[i], n)) OC.push_back(O[i]);
int lgp = 2;
for(int i = 0; i < n - 2; ++i) {
if(cmp(O[i], O[i + 2]))
lgp = i + 2;
else break;
}
for(int i = lgp; i >= max(lgp-2, 3); --i) if(is_cand(O[i], n)) OC.push_back(O[i]);
int zero;
if(OC.size() == 2)
zero = cmp(OC[0], OC[1]) ? OC[0] : OC[1];
else zero = OC[0];
//printf("Det0: %d\n", da::query_count);
vector<int> NewO;
NewO.push_back(zero);
for(int i = 0; i < n; ++i)
if(O[i] != zero) NewO.push_back(O[i]);
int start = 1;
for(int i = 1; i < n; ++i) {
if(cmp(NewO[start-1], NewO[i])) { // urmatorul
reverse(NewO.data() + start, NewO.data() + i + 1);
start = i + 1;
}
}
vector<int> R(n);
//printf("Fin: %d\n", da::query_count);
// for(int i = 0; i < n; ++i) cerr << R[i] << " "; cerr << "\n";
//for(int i = 0; i < n; ++i) cerr << NewO[i] << " "; cerr << "\n";
for(int i = 0; i < n; ++i) R[NewO[i]] = i;
return R;
}
