#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
vector <int> merge(vector <int> A,vector <int> B){
vector <int> C;
while(A.size()>0&&B.size()>0){
if(Query(A.back(),B.back())==0){
C.push_back(A.back());
A.pop_back();
}
else{
C.push_back(B.back());
B.pop_back();
}
}
while(B.size()>0){
C.push_back(B.back());
B.pop_back();
}
while(A.size()>0){
C.push_back(A.back());
A.pop_back();
}
reverse(C.begin(),C.end());
return C;
}
vector <int> sort(vector <int> v){
if(v.size()<=1) return v;
vector <int> A,B;
for(int i=0;i<v.size()/2;i++){
A.push_back(v[i]);
}
for(int i=v.size()/2;i<v.size();i++){
B.push_back(v[i]);
}
A=sort(A);
B=sort(B);
return merge(A,B);
}
std::vector<int> Solve(int N) {
vector<int> arr;
for(int i=0;i<N;i++) arr.push_back(i);
arr=sort(arr);
reverse(arr.begin(),arr.end());
// for(int i=0;i<N;i++) cout<<arr[i]<<" ";
// cout<<endl;
for(int i=0;i<N;i++){
if(i==N-1) break;
//cout<<i<<endl;
int bg=i;
//cout<<arr[bg]<<" "<<arr[bg+2]<<" "<<Query(arr[bg],arr[bg+2])<<endl;
while(bg!=N-1&&Query(arr[bg],arr[bg+2])==1){
bg+=2;
}
int r;
//cout<<i<<" "<<bg<<endl;
if(bg==i&&bg!=N-1) bg++;
else{
if(bg!=N-1&&Query(arr[bg-1],arr[bg+1])==1) bg++;
}
if(bg-i+1==3&&bg==N-1){
//cout<<"YES"<<endl;
if(Query(arr[i-1],arr[N-1])==1) reverse(arr.begin()+i,arr.begin()+bg+1);
else reverse(arr.begin()+i,arr.begin()+bg);
}
else reverse(arr.begin()+i,arr.begin()+bg+1);
i=bg;
}
// for(int i=0;i<N;i++) cout<<arr[i]<<" ";
// cout<<endl;
vector <int> ans(N);
for(int i=0;i<N;i++) ans[arr[i]]=i;
// cout<<endl;
return ans;
}
