가장 긴 감소하는 부분 수열

• 가장 긴 증가하는 부분 수열 (Longest Increasing Subsequence / LIS)을 구하는 알고리즘에서 부등호 방향만 바꿔주면 된다.
• 그러나 bisect 모듈에서는 커스텀 비교함수를 따로 받지 않기 때문에, 이 경우에는 그냥 값들에 -를 붙여서 넘기는 것으로 처리했다.
  • 실제로 가장 긴 증가하는 부분 수열 2에서 3바이트만 추가하면 이 코드가 된다.
• 시간 복잡도는 O(nlogn)

"""Solution code for "BOJ 11722. 가장 긴 감소하는 부분 수열".

- Problem link: https://www.acmicpc.net/problem/11722
- Solution link: http://www.teferi.net/ps/problems/boj/11722

Tags: [LIS] [BinarySearch]
"""

import bisect


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    arr = []
    for a_i in A:
        pos = bisect.bisect_left(arr, -a_i)
        if pos == len(arr):
            arr.append(-a_i)
        else:
            arr[pos] = -a_i

    print(len(arr))


if __name__ == '__main__':
    main()