a[10030],s=1e4,k,n,*p;main(j){for(a[1]=scanf("%d",&n);s--;p--)for(p=a;p++<a+n;j=!*p||(!p[j]|p[j]>*p?p[j]=1+*p:0,!p[-j]|p[-j]>*p?p[-j]=1+*p:1))for(k=p-a;k&=k-1;)j++;n=!printf("%d",*p-!*p);}