#include "monster.h"
#include <bits/stdc++.h>
namespace monster{
int N;
std::map<std::pair<int, int>, int> memo;
bool ask(int a, int b) {
bool isSw = false;
if (a > b) {
isSw = true;
std::swap(a, b);
}
if (memo.find({a, b}) == memo.end()) {
memo[{a, b}] = Query(a, b);
}
return memo[{a, b}] ^ isSw;
}
std::vector<int> Solve(int n_) {
N = n_;
std::vector<int> res(N);
std::iota(res.begin(), res.end(), 0);
auto mergeSort = [&](auto &&self, int l, int r) -> void {
if (r - l == 1) {
return;
}
const int m = (l + r) / 2;
self(self, l, m);
self(self, m, r);
std::vector<int> lVec, rVec;
std::copy(res.begin() + l, res.begin() + m, std::back_inserter(lVec));
std::copy(res.begin() + m, res.begin() + r, std::back_inserter(rVec));
std::vector<int> mergedVec;
int i = 0, j = 0;
while (i != m - l and j != r - m) {
if (not ask(lVec[i], rVec[j])) {
mergedVec.push_back(lVec[i++]);
} else {
mergedVec.push_back(rVec[j++]);
}
}
if (i != m - l) {
std::copy(lVec.begin() + i, lVec.end(), std::back_inserter(mergedVec));
}
if (j != r - m) {
std::copy(rVec.begin() + j, rVec.end(), std::back_inserter(mergedVec));
}
std::copy(mergedVec.begin(), mergedVec.end(), res.begin() + l);
};
mergeSort(mergeSort, 0, N);
std::vector<bool> isF(N);
isF[0] = true;
int l = -1, r = -1;
// find the first block!
std::vector<int> countWin;
for (int i = 0; i < std::min(N, 20); ++i) {
int c = 0;
for (int j = 0; j < std::min(N, 20); ++j) {
if (i == j) continue;
if (ask(res[i], res[j])) {
++c;
}
}
if (i == 0 or countWin.back() >= c) {
countWin.push_back(c);
} else {
break;
}
}
if (countWin.size() == 1) {
l = 0;
r = 1;
} else if (countWin.size() == 2) {
assert(countWin[0] == countWin[1] and countWin[0] == 1);
if (not ask(res[0], res[1])) {
l = 0;
r = 2;
} else {
isF[1] = true;
l = 1;
r = 2;
}
} else {
l = 0;
r = (int)countWin.size();
}
while (r != N) {
isF[r] = true;
bool fin = false;
for (int i = r; i < N; ++i) {
if (ask(res[l], res[i])) {
fin = true;
l = r;
r = i + 1;
break;
}
}
if (not fin) {
break;
}
}
std::vector<int> answer;
std::stack<int> stk;
for (int i = 0; i < N; ++i) {
if (isF[i]) {
while (not stk.empty()) {
answer.push_back(stk.top());
stk.pop();
}
}
stk.push(res[i]);
}
while (not stk.empty()) {
answer.push_back(stk.top());
stk.pop();
}
memo.clear();
std::vector<int> tet(N);
for (int i = 0; i < N; ++i) {
tet[answer[i]] = i;
}
return tet;
}
}
std::vector<int> Solve(int n_) {
return monster::Solve(n_);
}
/*
#include <cstdio>
#include <cstdlib>
using std::exit;
using std::fprintf;
using std::printf;
using std::scanf;
constexpr int Q_MAX = 25000;
constexpr int N_MAX = 1'000;
int N;
int S[N_MAX];
int query_count = 0;
void WrongAnswer(int code) {
printf("Wrong Answer [%d]\n", code);
exit(0);
}
bool Query(int a, int b) {
if (++query_count > Q_MAX) WrongAnswer(6);
if (a < 0 || N <= a || b < 0 || N <= b) WrongAnswer(4);
if (a == b) WrongAnswer(5);
return (S[a] > S[b]) ^ (abs(S[a] - S[b]) == 1);
}
void main_() {
if (scanf("%d", &N) != 1) {
fprintf(stderr, "Error while reading.\n");
exit(1);
}
for (int i = 0; i < N; i++) {
if (scanf("%d", S + i) != 1) {
fprintf(stderr, "Error while reading.\n");
exit(1);
}
}
N = 1000;
int cas = 1000;
std::mt19937 mt(100);
std::uniform_int_distribution dist(1, N);
std::vector<int> A(N);
std::iota(A.begin(), A.end(), 0);
int mav = 0;
while (cas--) {
std::shuffle(A.begin(), A.end(), mt);
for (int i = 0; i < N; ++i) S[i] = A[i];
const auto T = Solve(N);
if (T != A) {
std::cout << "bad" << std::endl;
}
mav = std::max(mav, query_count);
query_count = 0;
}
std::cout << mav << std::endl;
std::vector<int> T = Solve(N);
if ((int)T.size() != N) WrongAnswer(1);
for (int i = 0; i < N; ++i) {
std::cout << S[T[i]] << ' ';
}
std::cout << std::endl;
for (int i = 0; i < N; i++) {
if (T[i] < 0 || N <= T[i]) WrongAnswer(2);
if (T[i] != S[i]) WrongAnswer(3);
}
printf("Accepted: %d\n", query_count);
return;
}
int main() {
main_();
}*/
