#include "xylophone.h"
int arr[5001];
int zero(int x){
return (x>0)?x:-x;
}
void solve(int N) {
int s = 1, e = N, m;
while(s<e){
m = (s+e)/2+1;
if(query(m, N)==N-1) s = m;
else e = m-1;
}
arr[s] = 1;
if(s!=1){
arr[s-1] = query(s-1, s) + 1;
}
for(int i=s-2; i>=1; i--){
int t = query(i, i+2);
if(t==zero(arr[i+1]-arr[i+2])){
int k = query(i, i+1);
if(arr[i+1]>arr[i+2]){
arr[i] = arr[i+1] - k;
}else{
arr[i] = arr[i+1] + k;
}
}else{
int k = query(i, i+1);
if(arr[i+1]>arr[i+2]){
arr[i] = arr[i+1] + k;
}else{
arr[i] = arr[i+1] - k;
}
}
}
if(s!=N){
arr[s+1] = query(s, s+1) + 1;
}
for(int i=s+2; i<=N; i++){
int t = query(i-2, i);
if(t==zero(arr[i-1]- arr[i-2])){
int k = query(i-1, i);
if(arr[i-1]>arr[i-2]){
arr[i] = arr[i-1] - k;
}else{
arr[i]= arr[i-1] + k;
}
}else{
int k = query(i-1, i);
if(arr[i-1]>arr[i-2]){
arr[i] = arr[i-1]+k;
}else{
arr[i] = arr[i-1]-k;
}
}
}
for(int i=1; i<=N; i++){
answer(i, arr[i]);
}
}
