题解 | #Redraiment的走法#

import bisect #引入二分法
# 最大上升子序LIS
def lengthOfLIS(lst):
    
    arr = [lst[0]] #定义列表，将传入函数的列表第一个元素放入当前元素
    dp = [1]*len(lst) #定义一个列表，默认子序列有当前元素1，长度是传入函数的列表长度
    for i in range(1,len(lst)): #从第二个元素开始查找
        if lst[i] > arr[-1]: #如果元素大于arr列表的最后一个元素，就把它插入列表末尾
            arr.append(lst[i])
            dp[i] = len(arr)# 获取这个元素子序列的长度
        else: # 否则，利用二分法找到比元素大的元素的位置，用新的元素替代比它大的那个元素的值，这样就能制造出一个顺序排列的子序列
            pos = bisect.bisect_left(arr, lst[i])
            arr[pos] = lst[i]
            dp[i] =pos+1 # 获取这个元素子序列的长度
    return max(dp)

#二分法排序，将对应长度的最后一个数字放到列表里
#     n = len(lst)
#     if n <= 1:
#         return n
#     temp = [0] * n
#     temp[0] = lst[0]
#     l = 1
#     for i in range(1,n):
#         left = 0
#         right = l
#         if lst[i] > temp[l-1]:
#             temp[l]=lst[i]
#             l+=1
#             print(temp)
#             continue
#         while left < right:
#             index = (left+right)//2
#             if lst[i] > temp[index]:
#                 left = index +1 
#             else:
#                 right = index
#         temp[left] = lst[i]
#         print(temp)
#     print(temp)
#     return l

#常规做法
#     dp = [1] * len(lst)
#     for i in range(len(lst)):
#         for j in range(i):
#             if lst[i] > lst[j]:
#                 dp[i] = max(dp[i], dp[j] + 1)
#     return max(dp)

while True:
    try:
        n, nums = int(input()), list(map(int, input().split()))
        print(lengthOfLIS(nums))
    except:
        break