//W 896 最长上升子序列 II 
/*
    解题思路：类似贪心的DP  O(n logn)

    先看下之前的最长上升子序列的DP：

    解题思路：DP O(n2)

    状态表示：f[i]表示  以w[i]结尾的 上升子序列  的最大长度。

    状态转移：f[i] = max(f[j]) + 1。j∈(0,1,2,..,i-1),且满足 w[i] > w[j]

    f[i]最小值为1（自己为结尾） 

    在状态转移过程中： 找 f[j] 这里可以优化一下。 
    比如 f[j] 和 f[j-k] 如果都是3，且 w[j] < w[j-k]，就没必要再看f[j-k] 那个状态 
    即坚持这样的贪心原则：f[] 值 相同的前提下，只需保留 w[]值最小的那个状态！！！

    设置一个新的数组 d[]

    d[i]  表示 所有 长度为i的 上升子序列 的集合中  结尾能取到的最小值 
    d[i] 会自然的形成一个递增的数组  ：可以模拟下过程

    每次输入k，如果能找到 d[i] > k，则 d[i]=k 即长度i的序列应以 k结尾
              否则在数组 末尾+1 位置赋值 k      

    时间复杂度：每个输入的数字都用二分 找第一个大于它的位置，即 n*logn 

*/
#include <bits/stdc++.h>
using namespace std;
int d[100010];
int main( )
{
    int n,cnt=1,w,index;
    cin>>n;
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=n;i++)
    {
        cin>>w;
        index=lower_bound(d+1,d+1+cnt,w)-d;
        if(index<=cnt)
        {
            d[index]=w;
        }
        else
        {
            d[index]=w;
            cnt++;
        }
    }
    cout<<cnt;
    return 0;
}