#include<bits/stdc++.h>
using namespace std;
#include "xylophone.h"
int ans[100001] = {};
int used[100001] = {};
#define MID ((l+r)/2)
void solve(int N) {
// Find 1
int pos=0;
int l=1, r=N-1;
int mm=-1;
while(l<=r){
//cout<<MID<<" "<<N<<endl;
int q = query(MID, N);
if(q==N-1) mm=MID, l = MID+1;
else r = MID-1;
}
pos=mm;
//cout<<pos<<endl;
ans[pos] = 1;
used[1] = true;
ans[pos+1] = 1+query(pos, pos+1);
used[ans[pos+1]] = true;
if(pos>=2) ans[pos-1] = 1+query(pos-1, pos), used[ans[pos-1]]=true;
bool inc=false;
for(int i=pos+2;i<=N;i++){
int p=query(i-1, i);
if(ans[i-1]+p>N){
ans[i] = ans[i-1]-p;
inc = ans[i]<ans[i-1];
continue;
}
else if(ans[i-1]-p<=0){
ans[i] = ans[i-1]+p;
inc = ans[i]<ans[i-1];
continue;
}
int pp = query(i-2, i);
if(inc){
if(p>=pp || pp==abs(ans[i-1]-ans[i-2])) ans[i] = ans[i-1] + p;
else ans[i] = ans[i-1]-p;
}
else{
if(p>=pp || pp==abs(ans[i-1]-ans[i-2])) ans[i] = ans[i-1] - p;
else ans[i] = ans[i-1]+p;
}
inc = ans[i]<ans[i-1];
//cout<<i<<" "<<ans[i]<<endl;
}
inc = false;
for(int i=pos-2;i>0;i--){
int p=query(i, i+1);
if(ans[i+1]+p>N && !used[ans[i+1]+p]){
ans[i] = ans[i+1]-p;
inc = ans[i]<ans[i+1];
used[ans[i]] = true;
continue;
}
else if(ans[i+1]-p<=0 && !used[ans[i+1]-p]){
ans[i] = ans[i+1]+p;
inc = ans[i]<ans[i+1];
used[ans[i]] = true;
continue;
}
int pp = query(i, i+2);
if(inc){
if(p>=pp || pp==abs(ans[i+2]-ans[i+1])) ans[i] = ans[i+1] + p;
else ans[i] = ans[i+1]-p;
}
else{
if(p>=pp || pp==abs(ans[i+2]-ans[i+1])) ans[i] = ans[i+1] - p;
else ans[i] = ans[i+1]+p;
}
used[ans[i]] = true;
inc = ans[i]<ans[i+1];
//cout<<i<<" "<<ans[i]<<endl;
}
//cout<<endl;
for(int i = 1; i <= N; i++) {
//cout<<i<<" "<<ans[i]<<endl;
answer(i, ans[i]);
}
}
