#include "xylophone.h"
using namespace std;
static int a[5005];
void get_val(int st,int dr,int st_val,int dr_val,int target_val,bool mode){
if(st == dr){
return ;
}
int l = st,r = dr;
if(st_val != -1){
while(r - l > 1){
int mid = (l + r) / 2;
if(query(st,mid) < target_val){
l = mid;
}
else{
r = mid;
}
}
a[r] = st_val + (mode == false ? -1:1) * target_val;
get_val(st + 1,r,-1,a[r],query(st + 1,r),!mode);
get_val(r,dr,a[r],-1,query(r,dr),!mode);
}
else{
while(r - l > 1){
int mid = (l + r) / 2;
if(query(mid,dr) < target_val){
r = mid;
}
else{
l = mid;
}
}
a[l] = dr_val + (mode == false ? -1:1) * target_val;
get_val(st,l,-1,a[l],query(st,l),!mode);
get_val(l,dr - 1,a[l],-1,query(l,dr - 1),!mode);
}
}
void solve(int n) {
int l = 1,r = n;
while(r - l > 1){
int mid = (l + r) / 2;
if(query(1,mid) == n - 1){
r = mid;
}
else{
l = mid;
}
}
int pos_n = r;
a[pos_n] = n;
get_val(1,pos_n,-1,n,query(1,pos_n),false);
get_val(pos_n,n,n,-1,query(pos_n,n),false);
for(int i = 1;i <= n;i++){
answer(i,a[i]);
}
}
