#include "xylophone.h"
// #include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
static int ans[5000];
int v[5000];
void solve(int n) {
int idx=-1;
int l=1,r=n;
int cnt=0;
while(l<=r)
{
int mid=(l+r)/2;
int value=query(mid,n);
cnt++;
if(value!=(n-1))
r=mid-1;
else l=mid+1,idx=mid-1;
}
for(int i=1;i<n;i++)
v[i]=query(i,i+1),cnt++;
ans[idx]=1;
if((idx-1)>=0)
ans[idx-1]=v[idx]+1;
if((idx+1)<n)
ans[idx+1]=v[idx+1]+1;
map<int,int>mp;
mp[1]++;
for(int i=idx-2;i>=0;i--)
{
if((ans[i+1]+v[i+1])>n)
{
ans[i]=ans[i+1]-v[i+1];
mp[ans[i]]++;
continue;
}
// cout<<"HI"<<endl;
if((ans[i+1]-v[i+1])<=0)
{
ans[i]=v[i+1]+ans[i+1];
mp[ans[i]]++;
continue;
}
int a=ans[i+1],b=ans[i+2];
int v1=v[i+1]+ans[i+1],v2=ans[i+1]-v[i+1];
if(mp[v1])
{
ans[i]=v2;
continue;
}
if(mp[v2])
{
ans[i]=v1;
continue;
}
int value=query(i+1,i+3);
cnt++;
// cout<<i<<" "<<a<<" "<<b<<endl;
if((v1!=a)&&(v1!=b)&&(v2!=a)&&(v2!=b))
assert((max({a,b,v1})-min({a,b,v1}))!=((max({a,b,v2})-min({a,b,v2}))));
if(((max({a,b,v1})-min({a,b,v1}))==value)&&(v1!=a)&&(v1!=b)&&(v1>0)&&(v1<=n))
ans[i]=v1;
else ans[i]=v2;
mp[ans[i]]++;
}
// for(int i=0;i<n;i++)cout<<ans[i]<<" ";
// cout<<endl;
for(int i=idx+2;i<n;i++)
{
if((ans[i-1]+v[i])>n)
{
ans[i]=ans[i-1]-v[i];
mp[ans[i]]++;
continue;
}
if((ans[i-1]-v[i])<=0)
{
ans[i]=v[i]+ans[i-1];
mp[ans[i]]++;
continue;
}
int a=ans[i-1],b=ans[i-2];
int v1=v[i]+ans[i-1],v2=ans[i-1]-v[i];
if(mp[v1])
{
ans[i]=v2;
continue;
}
if(mp[v2])
{
ans[i]=v1;
continue;
}
int value=query(i-1,i+1);
if((v1!=a)&&(v1!=b)&&(v2!=a)&&(v2!=b))
assert((max({a,b,v1})-min({a,b,v1}))!=((max({a,b,v2})-min({a,b,v2}))));
if(((max({a,b,v1})-min({a,b,v1}))==value)&&(v1!=a)&&(v1!=b))
ans[i]=v1;
else ans[i]=v2;
mp[ans[i]]++;
}
// ans[0]=0;
assert(cnt<=7500);
for(int i=1;i<=n;i++){
// cout<<ans[i-1]<<" ";
answer(i,ans[i-1]);
}
}
