#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;){
// i-1 is all good
if(i == N-1)break;
cout << "start at: " << i << endl;
for(auto i:T)cout << i << " ";cout << endl;
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
// if(N-1 == i+2){
// // 3
// }else if(N-1 == i+3){
// }else{
// reverse(T.begin()+i,T.begin()+j-1+1);
// }
// }else{
if(j == i+2){
/*
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: 0 2 1 4 3
case2: 0 1 4 3 2
is zero:
case1: 1 0 3 2
case2: 0 3 2 1
*/
if(i != 0){
// finding the smallest(the one T[i-1] > T[i+1])
if(ask(T[i-1],T[i+1])){
reverse(T.begin()+i,T.begin()+i+1+1);
}else{
// not reverse
i = i+1;
continue;
}
}else{
if(ask(T[i+1],T[i+3])){
// not reverse
i = i+1;
continue;
}else{
reverse(T.begin()+i,T.begin()+i+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: 0 3 2 1 5 4
case1: 0 2 1 3 5 4
case1: 0 1 3 2 5 4
is zero:
case1: 2 1 0 4 3
case2: 1 0 2 4 3
case3: 0 2 1 4 3
^
*/
if(i != 0){
// finding the smallest(the one T[i-1] > it)
if(ask(T[i-1],T[i+2])){
reverse(T.begin()+i,T.begin()+i+2+1);
}else if(ask(T[i-1],T[i+1])){
reverse(T.begin()+i,T.begin()+i+1+1);
}else{
reverse(T.begin()+i+1,T.begin()+j+1);
}
}else{
int k = j+1;
while(ask(T[i],T[k]) == ask(T[i+1],T[k]) && ask(T[i+1],T[k]) == ask(T[i+2],T[k])) k++;
cerr << "3: " << i << " " << j << " " << k << endl;
// finding the biggest, the one > T[k];
if(ask(T[i],T[k])){
reverse(T.begin()+i,T.begin()+i+2+1);
}else if(ask(T[i+2],T[k])){
reverse(T.begin()+i,T.begin()+i+1+1);
}else{
reverse(T.begin()+i+1,T.begin()+i+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;
}
/*
testcase:
10
5 1 2 7 8 6 4 9 0 3
10
0 9 1 8 2 7 3 6 4 5
7
0 1 2 3 4 5 6
7
0 2 4 6 1 3 5
*/
