"""
基本思想：
    如果一个数可以接到3的后面，那么这个数一定可以接到1的后面，所以可以新建一个数组s，用来存储所有相同长度的子序列的结尾的最小元素
步骤：
    遍历输入数组nums，然后二分查找q数组中小于nums[i]的最大的结尾元素的索引

输入示例：
7
3 1 2 1 8 5 6

输出样例：
4
"""
# 输入示例
n = int(input().strip())
nums = [0]
nums.extend(list(map(int, input().split())))

q = [2e-9]    # q数组用来存储长度为index的所有子序列中的最小值，初始化q数组的第0个元素为2e-9是因为题中最小值为1e-9，这样可以保证任意一个元素的长度为1
for i in range(1,n+1):
    q.append(0)   # q数组填0补位

length = 0    # 记录q数组的长度（不包含填充的最小值：2e-9）
for i in range(1,n+1):    # 遍历nums的元素
    l = 0    # 必须从0开始，为什么从1开始不行？？？
    r = length
    while l<r:    # 对q数组进行二分查找，查找q中小于nums[i]的最大值
        mid = (l+r+1)>>1    # ！！！出错：后面l=mid时，前面必须是mid = (l+r+1)>>1，否则会出现死循环
        if q[mid]<nums[i]:
            l = mid
        else:
            r = mid - 1
    length = max(length, r + 1)    # ???更新length,其中r是找到的q数组中小于nums[i]的最大数的索引，因为nums[i]大于q[length],所以r要加1
    q[r+1] = nums[i]    # 更新长度为r+1的子序列中最后一个元素的最小值
print(length)