#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int n,i,j,lmax,p,min1;
int x[5001],l[5001],fol[5001];
int main()
{
    f>>n; f>>x[1]; fol[1]=0; l[1]=1;
    for(i=2;i<=n;i++){
        f>>x[i]; lmax=0; p=0;
        for(j=1;j<=i-1;j++){
            if(x[i]>x[j]&&lmax<l[j]){ lmax=l[j]; }
            if(x[i]>x[j]) fol[j]=1;
        }
        if(lmax!=0) {
            l[i]=lmax+1;
            //fol[p]=1;
        } else l[i]=1;
    }
    //for(i=1;i<=n;i++) g<<l[i]<<' '<<fol[i]<<'\n';
    min1=n+1;
    for(i=1;i<=n;i++){
        if(min1>l[i]&&fol[i]==0) min1=l[i];
    }
    g<<min1<<'\n';
    return 0;
}