#include <bits/stdc++.h>
#include "monster.h"
using namespace std;
typedef long long ll;
namespace {
int n;
int arr[1002];
int arr2[1002];
void Sort(int l, int r){
if(l>=r) return;
int m = (l+r)>>1;
Sort(l, m);
Sort(m+1, r);
for(int i=l; i<=r; i++) arr2[i] = arr[i];
for(int i=l, j=m+1, k=l; k<=r; k++){
if(i==m+1) arr[k] = arr2[j++];
else if(j==r+1) arr[k] = arr2[i++];
else if(Query(arr2[i], arr2[j]) == 0) arr[k] = arr2[i++];
else arr[k] = arr2[j++];
}
}
void calculateElse(int tmp, int st){
for(int i=st; i<n; i++){
if(Query(arr[tmp], arr[i])){
reverse(arr+tmp+1, arr+i+1);
tmp = i;
}
}
}
void Reorder(int l, int r){
if((r-l) <= 7){
int cnt[1005] = {0};
for(int i=l; i<=r; i++){
for(int j=i+1; j<=r; j++){
if(Query(arr[i], arr[j])) cnt[arr[i]]++;
else cnt[arr[j]]++;
}
}
sort(arr+l, arr+r+1, [&](int x, int y){
return cnt[x] < cnt[y];
});
if(Query(arr[l], arr[l+1]) == 0) swap(arr[l], arr[l+1]);
if(Query(arr[r], arr[r-1])) swap(arr[r], arr[r-1]);
return;
}
int comp[1005] = {0};
int cnt = 0;
int lim = r;
for(int i=l+1; i<=r; i++){
if(Query(arr[l], arr[i])) comp[i] = 1, cnt++;
if(comp[i-1] && !comp[i]){
lim = i-1;
break;
}
}
if(cnt >= 2){ /// Case 1
assert(lim >= l+3);
if(Query(arr[lim], arr[lim-2])) reverse(arr+l, arr+lim);
else reverse(arr+l, arr+lim+1);
calculateElse(lim, lim+1);
return;
}
else if(lim >= l+3){ /// Case 2
if(Query(arr[l+1], arr[lim])) reverse(arr+l+1, arr+lim+1);
else reverse(arr+l+2, arr+lim+1), swap(arr[l], arr[l+1]);
calculateElse(lim, lim+1);
}
else if(lim==1){ /// Case 3
Reorder(l+2, r);
}
else{ /// Case 4
Reorder(l+3, r);
if(Query(arr[l], arr[l+3])){
reverse(arr+l, arr+l+3);
}
else if(Query(arr[l+1], arr[l+3])){
swap(arr[l+1], arr[l+2]);
}
else{
swap(arr[l], arr[l+1]);
}
}
}
}
vector<int> Solve(int N){
n = N;
for(int i=0; i<n; i++) arr[i] = i;
random_shuffle(arr, arr+n);
Sort(0, n-1);
Reorder(0, n-1);
// for(int i=0; i<n; i++) printf("%d ", arr[i]);
// puts("");
vector<int> idx (n);
for(int i=0; i<n; i++) idx[arr[i]] = i;
return idx;
}
