#include<iostream>
using namespace std;
const int N = 100109;
int a[N], q[N];  //q[i]是所有长度为i的最长上升子序列中的最后一个元素的最小值,q[]元素严格单调递增
int n, len;  // len 是当前最长上升子序列的长度
int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    q[0] = -1e9;  //不存在长度为0的子序列
    for(int i = 1; i <= n; i ++)  //遍历每个元素，看看它适合插在哪个子序列里
    {
        int l = 0, r = len;
        while(l < r)  //二分找q[]中比a[i]的小的数中的最大值的下标， 即q[i] < a[i] < q[i+1]
        {
            int mid = l + r + 1 >> 1;  //mid在右，上取整
            if(q[mid] < a[i]) l = mid;
            else r = mid - 1;
        } // 找到的r就说明a[i]能接在长度为r的上升序列的后面，成为r+1长的上升子序列，且这个a[i]必定小于q[i+1]，故更优
        len = max(len, r + 1);
        q[r + 1] = a[i]; // 更新长度为r+1长的上升子序列所有末尾元素中的最小值
    }
    cout << len << endl;
    return 0;
}