1 #include <cstdio>
 2 #include <cmath>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <queue>
 6 #include <stack>
 7 #include <vector>
 8 #include <iostream>
 9 #include "algorithm"
10 #define mem(a,b) memset(a,b,sizeof(a))
11 using namespace std;
12 typedef long long LL;
13 const int MAX=100005;
14 int n;
15 int a[MAX],f[MAX];
16 int main(){
17     freopen ("manage.in","r",stdin);
18     freopen ("manage.out","w",stdout);
19     int i,j;
20     int low,high,mid,len;
21     scanf("%d",&n);
22     for (i=1;i<=n;i++)
23      scanf("%d",a+i);
24     len=0;
25     for (i=1;i<=n;i++){
26         if (a[i]>f[len])
27             f[++len]=a[i];
28         else{
29             low=1;high=len-1;
30             while (low<=high){
31                 mid=(low+high)>>1;
32                 if (f[mid]<=a[i])
33                  low=mid+1;
34                 else
35                  high=mid-1;
36             }
37             f[low]=a[i];
38         }
39     }
40     printf("%d",len);
41     return 0;
42 }