#include <stdio.h>

 #include <string.h>

 #include <algorithm>

 using namespace std;

 const int inf=0x3f3f3f3f;

 int main()

 {

     int n;

     int a[],b[];

     int dp1[],dp2[],num1[],num2[],num3[];

     int i,j,k;

     while(scanf("%d",&n)!=EOF)

     {

         for(i=;i<n;i++)

         {

             scanf("%d",&a[i]);

         }

         for(i=;i<n;i++)

         {

             dp1[i]=inf;

             dp2[i]=inf;

         }

         for(i=;i<n;i++)

             b[n-i-]=a[i];

         for(i=;i<n;i++)

         {

             int lower;

             lower=lower_bound(dp2,dp2+n,a[i])-dp2;

             num2[i]=lower+;

             dp2[lower]=a[i];

             lower=lower_bound(dp1,dp1+n,b[i])-dp1;

             num3[i]=lower+;

             dp1[lower]=b[i];

         }

         for(i=;i<n;i++)

             num1[n-i-]=num3[i];

         /*for(i=0;i<n;i++)

         {

             printf("%d ",num1[i]);

         }*/

         int ans=;

         for(i=;i<n;i++)

         {

             int mi=min(num1[i],num2[i]);

             if(mi>ans)

                 ans=mi;

         }

         printf("%d\n",ans*-);

     }

     return ;

 }