#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#include "cave.h"
using namespace std;
int n,a[5002],b[5002],door[5002],i,j;
/*
struct Interactive
{
int n=4,True[4]={ 1,1,1,0 },Door[4]={ 3,1,0,2 },d[5002];
int Try(int a[])
{
for(int i=0;i<n;i++)
if(a[i]==True[i]) d[Door[i]]=0; else d[Door[i]]=1;
for(int i=0;i<n;i++)
if(d[i]==1) return i;
return -1;
}
} IR;
int tryCombination(int a[])
{
for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<'\n';
return IR.Try(a);
}
void answer(int a[],int b[])
{
for(int i=0;i<n;i++) cout<<a[i]<<" ";
cout<<'\n';
for(int i=0;i<n;i++) cout<<b[i]<<" ";
}*/
int check_close(int u,int cnt,int ch)
{
for(int i=0;i<n;i++)
if(a[i+1]>-1) b[i]=a[i+1];
else if(cnt>0)
{
cnt--;
b[i]=ch;
}
else b[i]=0;
return tryCombination(b)+1==u;
}
void Work()
{
memset(a,-1,sizeof(a));
for(i=1;i<=n;i++)
{
int k=check_close(i,n-i+1,0),l=1,r=n-i+1;
while(l<r)
{
int mid=(l+r)>>1;
if(check_close(i,mid,1)!=k) r=mid; else l=mid+1;
}
for(j=1;j<=n;j++)
if(a[j]==-1)
{
l--;
if(l==0) break;
}
a[j]=k;
door[j-1]=i-1;
}
for(i=0;i<n;i++) b[i]=a[i+1];
answer(b,door);
}
void exploreCave(int _n)
{
n=_n;
Work();
}
/*
int main()
{
freopen("cave.inp","r",stdin);
freopen("cave.out","w",stdout);
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n;
exploreCave(n);
}
*/
