[이분탐색] 백준 3745 오름세(가장 긴 증가하는 부분수열)

# 가장 긴 증가하는 부분 수열
import sys
def find(x):
    l = 0
    r = len(result)-1
    while l<r:
        mid = (l+r)//2
        if result[mid]<x:
            l = mid + 1
        elif result[mid]>x:
            r = mid
        else:
            l = mid
            r = mid
    result[l]=x
    return
try:
    while True:
        N = int(sys.stdin.readline())
        P = list(map(int, sys.stdin.readline().split()))
        result = [0]
        for i in range(N):
            if result[-1]<P[i]:
                result.append(P[i])
            else:
                find(P[i])
        print(len(result)-1)
except ValueError:
    sys.exit()