#include <fstream>

using namespace std;
ifstream f("subsir2.in");
ofstream g("subsir2.out");
int a[5005],i,j,n,c[5005],p,t,d[5005],k,fiu[5005],mn,o;
int caut_bin(int x,int dr)
{
    int st=1,mij;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(x<=a[c[mij]]) dr=mij-1;
        else st=mij+1;
    }
    return dr+1;
}
void afis(int t)
{
    if(t>0)
    {
        int l=n;
        for(int i=k; i>=1; i--)
        if(fiu[i]==t)
            {
              l=i;
            }
        afis(l);
        g<<l<<" ";
    }
}
int main()
{
    f>>n;
    for(i=1; i<=n; i++) f>>a[i];
    for(i=1; i<=n; i++)
    {
        p=caut_bin(a[i],t);
        d[i]=p;
        if(p>t)
        {
            t++;
            c[t]=i;
        }
        else if(a[i]<a[c[p]]) c[p]=i;
        fiu[c[p-1]]=i;
    }
    mn=5005;
     for(i=1; i<=n; i++)
     {
         if(fiu[i]==0)
         {
             if(d[i]<mn) {mn=d[i];o=i;}
         }
     }
    k=n;
    g<<mn<<'\n';
    //afis(o);
    return 0;
}