#include "monster.h"
//#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
namespace {
bool example_variable;
} // namespace
vector<int> merge(vector<int> l, vector<int> r){
vector<int> res;
int i = 0, j = 0;
while (i < l.size() && j < r.size()){
if (!Query(l[i], r[j])){
res.push_back(l[i++]);
} else {
res.push_back(r[j++]);
}
}
while (i < l.size()) res.push_back(l[i++]);
while (j < r.size()) res.push_back(r[j++]);
return res;
}
vector<int> merge_sort(vector<int>& T) {
if (T.size() <= 1) return T;
int mid = T.size() / 2;
vector<int> left(T.begin(), T.begin() + mid);
vector<int> right(T.begin() + mid, T.end());
return merge(merge_sort(left), merge_sort(right));
}
std::vector<int> Solve(int N) {
std::vector<int> T(N);
for (int i = 0; i < N; i++) T[i] = i;
T = merge_sort(T);
vector<int> comp(N-1, 0);
int ncp = 0;
int gindex = -1;
for(int i=max(N-15, 0);i<N-1;++i) {
comp[i] = Query(T[i], T[N-1]); // 1 if T[i] is greater, 0 otherwise
ncp += comp[i];
if (comp[i]) gindex = i;
}
int findex = -1;
if (ncp > 1){
// findex is the index of the second 1 in comp
bool onefound = false;
for (int i = 0; i < N-1; i++) {
if (comp[i] == 1) {
if (onefound) {
findex = i;
break;
} else {
onefound = true;
}
}
}
}
else {
if (gindex <= N-4){
int cval = Query(T[gindex], T[N-2]);
if (cval == 1) findex = N-1;
else findex = N-2;
}
else{
int s = 0;
for(int i=max(N-15, 0);i<N-3;++i){
s += Query(T[i], T[N-2]);
}
if (s > 0) {
findex = N-1;
}
else {
findex = N-2;
}
}
}
int pindex = N-1;
while (findex >= 0){
// reverse between findex and pindex
reverse(T.begin() + findex, T.begin() + pindex + 1);
if (findex == 0) break;
int c = -1;
for(int i=findex-1; i >= 0; --i) {
int d = Query(T[i], T[findex]);
if (d == 1) {
c = i;
break;
}
}
pindex = findex - 1;
findex = c;
}
vector<int> S(N);
// S is the inverse of T
for (int i = 0; i < N; i++) {
S[T[i]] = i;
}
//output s
/*
for (int i = 0; i < N; i++) {
cout << S[i] << " ";
}
cout << endl;*/
return S;
}
