====== 가장 긴 증가하는 부분 수열 2 ======

===== 풀이 =====
  * [[ps:가장 긴 증가하는 부분 수열]]문제의 기본 문제. 링크에 설명된대로, 이진탐색 방법과 세그먼트 트리 방법의 두가지의 O(nlogn) 알고리즘이 있다.
  * 여기에서는 이진탐색 방법으로 풀었다. 세그먼트 트리 방법의 풀이는 [[ps:problems:boj:11053]] 참고

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 12015. 가장 긴 증가하는 부분 수열 2".

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

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()
</dkpr>

{{tag>BOJ ps:problems:boj:골드_2}}