가장 긴 증가하는 부분 수열 (이분 탐색)

N개의 수열이 주어진다. 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하라. O(N log N) 이분 탐색으로 구현하라.

보조 배열 d를 유지하되 각 원소를 d에서 하한 이분 탐색으로 삽입 위치를 찾아 교체한다. d의 길이가 LIS 길이다.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100,000)

둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. (1 ≤ 각 수 ≤ 1,000,000)

출력

LIS의 길이를 출력하라.

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4