/*

 题意：

 给定L个整数A1,A2，...，An，按照从左到右的顺序选出尽量多的整数，

 组成一个上升序列（子序列可以理解为：删除0个或者多个数，其他的数的吮吸不变）。

 例如，1，6，2，3，7，5，可以选出上升子序列1，2，3，5，也可以选出1，6，7，

 但前者更长，选出的上升子序列中相邻元素不能相等。

 思路：

 开辟一个栈，每次取栈顶元素s和读到的元素a做比较，如果a>s，  则加入栈；

 如果a<s，则二分查找栈中的比a大的第1个数，并替换。  最后序列长度为栈的长度。

 */

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int a[];

 int main()

 {

     int n,u,k;

     while(cin>>n)

     {

         a[]=-;

         k=;

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

         {

             cin>>u;

             if(a[k]<u)

             {

                 a[++k]=u;

             }

             else

             {

                 int l=,r=k,mid;

                 while(l<=r)

                 {

                     mid=l+(r-l)/;

                     if(u>a[mid])

                         l=mid+;

                     else

                         r=mid-;

                 }

                 a[l]=u;

             }

         }

         cout<<k<<endl;

     }

 }

 #include <stdio.h>

 #include <string.h>

 //author:YangSir

 int a[];

 int main(){

     int n,i,max,b,num,x;

     while(~scanf("%d",&n)){

         num=;

         a[]=-;

         scanf("%d",&b);

         a[]=max=b;

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

             scanf("%d",&b);//数组的每个值变化的过程就表示子串一个个代入

             if(max<b){

                 max=b;

                 num++;

                 a[num]=max;//子串在增长

             }

             else{

                 x=num-;

                 while(a[x]>=b)

                     x--;

                 a[x+]=b;

             }

             max=a[num];//max可能会变

         }

         printf("%d\n",num);

     }

     return ;

 }

 #include<stdio.h>

 #include<algorithm>

 using namespace std;

 #define INF 1<<30

 int main()

 {

     int n, a[], dp[];

     while(~scanf("%d", &n))

     {

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

         {

             scanf("%d", a+i);

             dp[i] = INF;

         }

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

             *lower_bound(dp, dp+n, a[i]) = a[i];

         printf("%d\n", lower_bound(dp, dp+n, INF)-dp);

     }

     return ;

 }