import sys

In = sys.stdin.readline

from bisect import bisect_left


n=int(In())

arr = list(map(int, In().split()))

index = [0] * n

dp = [arr[0]]


for i in arr:

if dp[-1]

dp += [i]

else:

dp[bisect_left(dp,i)] = i

print(len(dp))


--------------------------------------------------------------


import sys

In = sys.stdin.readline


n = int(In())

arr = list(map(int, In().split()))

dp = [arr[0]]


for i in arr:

    if dp[-1]

        dp += [i]

    else:

        lo,hi = 0, len(dp)

        while lo

            mid = (lo+hi)//2

            if dp[mid]

            else: hi = mid

        dp[lo] = i

print(len(dp))

---------------------------------------------------------------

LIS 알고리즘인데 위에꺼는 100만개 기준으로 0.9초 걸리고

아래꺼는 3.6초 걸려

위랑 아래랑 똑같이 이진 탐색하는건데

왜 함수 호출 안하는 게 하는 것보다 느린지 이해가 안 돼