#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
static int A[5000];
void solve(int N)
{
int num=(N-1);
int ans[N];
int l=1,r=N;
while(l<=r)
{
int mid=(l+r)/2;
if(query(mid,N)==(N-1))
{
num=mid;
l=mid+1;
}
else
{
r=mid-1;
}
}
ans[num-1]=1;
set<int> st;
for(int i=2;i<=N;i++)
st.insert(i);
int a=num-1,b=num-1;
if(num-1>=1)
ans[num-2]=query(num-1,num)+1;
if(num+1<=N)
ans[num]=query(num,num+1)+1;
while(a>=2||b<=(N-3))
{
if((a-2)>=0&&ans[a-1]==(*st.rbegin()))
{
ans[a-2]=ans[a-1]-query(a-1,a);
a--;
st.erase(ans[a]);
}
else if(b<=(N-3)&&ans[b+1]==(*st.rbegin()))
{
ans[b+2]=ans[b+1]-query(b+2,b+3);
b++;
st.erase(ans[b]);
}
else if(b<=(N-3))
{
int y=query(b+2,b+3);
if(st.count(ans[b+1]-y)==0)
{
ans[b+2]=ans[b+1]+y;
b++;
st.erase(ans[b]);
continue;
}
else if(st.count(ans[b+1]+y)==0)
{
ans[b+2]=ans[b+1]-y;
b++;
st.erase(ans[b]);
continue;
}
int x=query(b+1,b+3);
if(x==y||x==abs(ans[b+1]-ans[b]))
{
if(ans[b]>ans[b+1])
{
ans[b+2]=ans[b+1]-y;
b++;
st.erase(ans[b]);
continue;
}
ans[b+2]=ans[b+1]+y;
b++;
st.erase(ans[b]);
continue;
}
else
{
if(ans[b]>ans[b+1])
{
ans[b+2]=ans[b+1]+y;
b++;
st.erase(ans[b]);
continue;
}
ans[b+2]=ans[b+1]-y;
b++;
st.erase(ans[b]);
continue;
}
}
else
{
int y=query(a-1,a);
if(st.count(ans[a-1]-y)==0)
{
ans[a-2]=ans[a-1]+y;
a--;
st.erase(ans[a]);
continue;
}
else if(st.count(ans[a-1]+y)==0)
{
ans[a-2]=ans[a-1]-y;
a--;
st.erase(ans[a]);
continue;
}
int x=query(a-1,a+1);
if(x==y||x==abs(ans[a-1]-ans[a]))
{
if(ans[a-1]>ans[a])
{
ans[a-2]=ans[a-1]-y;
a--;
st.erase(ans[a]);
continue;
}
ans[a-2]=ans[a-1]+y;
a--;
st.erase(ans[a]);
continue;
}
else
{
if(ans[a-1]>ans[a])
{
ans[a-2]=ans[a-1]+y;
a--;
st.erase(ans[a]);
continue;
}
ans[a-2]=ans[a-1]-y;
a--;
st.erase(ans[a]);
continue;
}
}
}
for(int i=1;i<=N;i++)
{
answer(i,ans[i-1]);
}
return;
}
