#include <fstream>

using namespace std;
ifstream fin("secv.in");
ofstream fout("secv.out");
int v[100001],a[100001],b[100001],d[100001];
int main()
{
   int n,i,nr=0,poz,mij,dr,st;
   fin>>n;
   for(i=1;i<=n;i++)
   {
       fin>>v[i];
   }a[++nr]=v[1];b[1]=1;
   d[1]=1;
   for(i=2;i<=n;i++)
   {
       st=1;dr=nr;

       if(v[i]>a[nr]){a[++nr]=v[i];b[i]=nr;}
       else{
       while(st<=dr)
       {
           mij=(st+dr)/2;
           if(a[mij]>v[i]){poz=mij;dr=mij-1;}
           else st=mij+1;
       }
       a[poz]=v[i];
       b[i]=poz;
       }
       d[i]=nr;


   }
   for(i=1;i<=n;i++)
{
   if(d[i]==1){poz=i;}
else break;

}int poz2;
for(i=n;i>=1;i--)
{
    if(d[i]==nr){poz2=i;}
    else break;
}fout<<poz2-poz+1;

    return 0;
}