#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
void solve(int N) {
int ans[N+1]={};
int l=1,r=N-1;
while(l+1<r){
int m=(l+r)/2;
if(query(m,N)==N-1)l=m;
else r=m;
}
if(l>1){
ans[l]=1;
ans[l-1]=query(l-1,l);
for(int i=l-2;i>0;i--){
int ix=query(i,i+1);
int iy=query(i,i+2);
if(ix==iy){
if(ans[i+1]<ans[i+2])ans[i]=ans[i+2]-iy;
else ans[i]=ans[i+2]+iy;
}else{
if(ans[i+1]<ans[i+2])ans[i]=ans[i+1]+ix;
else ans[i]=ans[i+1]-ix;
}
}
}
if(l<N){
ans[l]=1;
ans[l+1]=query(l,l+1);
for(int i=l+2;i<=N;i++){
int ix=query(i-2,i);
int iy=query(i-1,i);
if(ix==iy){
if(ans[i-2]<ans[i-1])ans[i]=ans[i-1]-iy;
else ans[i]=ans[i-1]+iy;
}else{
if(ans[i-2]<ans[i-1])ans[i]=ans[i-2]+ix;
else ans[i]=ans[i-2]-ix;
}
}
}
for(int i=1;i<=N;i++)
answer(i,ans[i]);
}
