#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
bool example_variable;
} // namespace
bool ask(int a,int b){
cerr << "? " << a << " " << b << endl;
return Query(a,b);
}
void merge_sort(int l,int r,vector<int>& T){
// terminate
if(l == r){
return;
}
// split
int m =(l+r)/2;
merge_sort(l,m,T);
merge_sort(m+1,r,T);
// combine;
vector<int> cur;
int a = l;
int b = m+1;
while(true){
if(a == m+1 || b == r+1){
// terminated;
if(a == m+1){
while(b != r+1){
cur.push_back(T[b]);
b++;
}
}else{
while(a != m+1){
cur.push_back(T[a]);
a++;
}
}
break;
}
if(ask(T[a],T[b])){
cur.push_back(T[b]);
b++;
}else{
cur.push_back(T[a]);
a++;
}
}
for(int i = 0;i < cur.size();i++){
T[l+i] = cur[i];
}
cerr << l << " " << r << "(" << cur.size() << "):";
for(int i = l;i <= r;i++)cerr << T[i] << " ";cerr << endl;
return;
}
vector<int> Solve(int N) {
vector<int> T(N);
for(int i = 0;i < N;i++){
T[i] = i;
}
merge_sort(0,N-1,T);
// T is merge_sort
for(auto i:T)cerr << i << " ";cerr << endl;
// swap(T[N-1],T[N-2]);
// for(int i = N-3;i >= 1;i--){
// if(!Query(T[i],T[i+1])){
// swap(T[i],T[i-1]);
// }
// }
/*
TODO: we obtain a arr that T[a] < T[b] , but it may be a subsequence that reverse
TODO: we are gonna check until T[a] > T[a+d] not hold (d > 1),and then reverse it
TODO: to determine if need to swap last, we check T[a+d] and T[a+d-2]
*/
for(int i = 0;i < N;){
int j = i+2;
while(j < N && ask(T[i],T[j])){
j++;
}
// reverse i~j-1 or i~j-2
if(j == N){
// T[i] > T[j-1], swap all
reverse(T.begin()+i,T.begin()+j-1+1);
}else{
if(j == i+2){
// must swap;
reverse(T.begin()+i,T.begin()+j-1+1);
}else if(j == i+3){
/*
cur i,i+1,i+2
how to know rev(i,i+2) or (i,i+1)
if(i != 0), we can check i-1,j-1
case1: 2 1 0 4 3
case2: 1 0 2 4 3
^
*/
if(i != 0){
if(ask(T[i-1],T[j-1])){
reverse(T.begin()+i,T.begin()+j-1+1);
}else{
reverse(T.begin()+i,T.begin()+j-2+1);
}
}else{
int k = j;
while(ask(T[i],T[k]) == ask(T[j-1],T[k])) k++;
cerr << "3: " << i << " " << j << " " << k << endl;
if(ask(T[i],T[k])){
reverse(T.begin()+i,T.begin()+j-1+1);
reverse(T.begin()+j,T.begin()+k+1);
}else{
reverse(T.begin()+i,T.begin()+j-2+1);
reverse(T.begin()+j,T.begin()+k+1);
}
i = k+1;
continue;
}
}else if(ask(T[j-1],T[j-3])){
// if T[j-1] > T[j-3], j-1 is fake;
reverse(T.begin()+i,T.begin()+j-2+1);
}else{
reverse(T.begin()+i,T.begin()+j-1+1);
}
}
i = j;
}
for(auto i:T)cerr << i << " ";cerr << endl;
vector<int> ans(N);
for(int i = 0;i < N;i++){
ans[T[i]] = i;
}
return ans;
}
