#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
long long n,sq[5069];
bitset<5069> vtd;
bool vld(long long x)
{
return x>0&&x<=n&&!vtd[x];
}
void fl(long long lh,long long rh,long long u)
{
long long i,k,l;
for(i=lh;i!=rh+u;i+=u)
{
k=query(min(i,i-u),max(i,i-u));
if(!vld(sq[i-u]-k))
{
sq[i]=sq[i-u]+k;
}
else if(!vld(sq[i-u]+k))
{
sq[i]=sq[i-u]-k;
}
else
{
l=query(min(i,i-u*2),max(i,i-u*2));
if(max(sq[i-u]+k,sq[i-u*2])-min(sq[i-u],sq[i-u*2])==l)
{
sq[i]=sq[i-u]+k;
}
else
{
sq[i]=sq[i-u]-k;
}
}
vtd[sq[i]]=1;
}
}
void solve(int on)
{
long long i,lh,rh,md,zz,st,fn;
n=on;
zz=1;
for(lh=2,rh=n-1;lh<=rh;)
{
md=(lh+rh)/2;
if(query(md,n)==n-1)
{
zz=md;
lh=md+1;
}
else
{
rh=md-1;
}
}
st=zz;
sq[st]=1;
vtd[1]=1;
zz=n;
for(lh=st+1,rh=n-1;lh<=rh;)
{
md=(lh+rh)/2;
if(query(1,md)==n-1)
{
zz=md;
rh=md-1;
}
else
{
lh=md+1;
}
}
fn=zz;
sq[fn]=n;
vtd[n]=1;
fl(st-1,1,-1);
fl(st+1,fn-1,1);
fl(fn+1,n,1);
for(i=1;i<=n;i++)
{
answer(i,sq[i]);
}
}
