#include<iostream>
#include "xylophone.h"
using namespace std;
bool bylo[100000];
int jaki[100000];
/*int query(int x,int y)
{
cout<<x<<" "<<y<<"\n";
int co;
cin>>co;
return co;
}
int answer(int x,int y)
{
cout<<y<<" ";
}*/
void solve(int n)
{
int pocz=1,kon=n+1,sre,ostd=n-1;
while(pocz<kon)
{
sre=(pocz+kon)/2;
int k=query(sre,n);
if(k==n-1)
{
ostd=sre;
pocz=sre+1;
}
else{
kon=sre;
}
}
jaki[ostd]=1;
bylo[1]=1;
for(int i=ostd+1;i<=n;i++)
{
int k=query(i-1,i);
if(jaki[i-1]-k<=0 || bylo[jaki[i-1]-k]==1)
jaki[i]=jaki[i-1]+k;
else if(jaki[i-1]+k>n || bylo[jaki[i-1]+k]==1)
jaki[i]=jaki[i-1]-k;
else{
int k1=query(i-2,i);
if(jaki[i-2]<jaki[i-1])
{
int odl=jaki[i-1]-jaki[i-2];
if(k1==odl+k)
jaki[i]=jaki[i-1]+k;
else jaki[i]=jaki[i-1]-k;
}
else{
int odl=jaki[i-2]-jaki[i-1];
if(k1==k+odl)
jaki[i]=jaki[i-1]-k;
else jaki[i]=jaki[i-1]+k;
}
}
bylo[jaki[i]]=1;
}
for(int i=ostd-1;i>=1;i--)
{
int k=query(i,i+1);
if(jaki[i+1]-k<=0 || bylo[jaki[i+1]-k]==1)
jaki[i]=jaki[i+1]+k;
else if(jaki[i+1]+k>n || bylo[jaki[i+1]+k]==1)
jaki[i]=jaki[i+1]-k;
else{
int k1=query(i,i+2);
if(jaki[i+2]<jaki[i+1])
{
int odl=jaki[i+1]-jaki[i+2];
if(k1==odl+k)
jaki[i]=jaki[i+1]+k;
else jaki[i]=jaki[i+1]-k;
}
else{
int odl=jaki[i+2]-jaki[i+1];
if(k1==k+odl)
jaki[i]=jaki[i+1]-k;
else jaki[i]=jaki[i+1]+k;
}
}
bylo[jaki[i]]=1;
}
for(int i=1;i<=n;i++)
answer(i,jaki[i]);
}
