#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
void solve(int N) {
int l=1,r=N,idx,mid;
vector<int> ans(N+1);
while(l<=r){
mid=(l+r)/2;
int x=query(1,mid);
if(x==N-1) idx=mid,r=mid-1;
else l=mid+1;
}
ans[idx]=N;
if(idx<N) ans[idx+1]=N-(query(idx,idx+1));
for(int i=idx+2;i<=N;i++){
int x=query(i-1,i),y=query(i-2,i);
if(max({ans[i-1],ans[i-2],ans[i-1]+x})-min({ans[i-1],ans[i-2],ans[i-1]+x})) ans[i]=ans[i-1]+x;
else ans[i]=ans[i-1]-x;
}
if(idx>1) ans[idx-1]=N-query(idx-1,idx);
for(int i=idx-2;i>0;i--){
int x=query(i,i+1),y=query(i,i+2);
if(max({ans[i+1],ans[i+2],ans[i+1]+x})-min({ans[i+1],ans[i+2],ans[i+1]+x})) ans[i]=ans[i+1]+x;
else ans[i]=ans[i+1]-x;
}
// for(int i=1;i<=N;i++) cout<<ans[i]<<" ";
for(int i=1;i<=N;i++) answer(i,ans[i]);
}
