최장 증가 수열 (대용량)

N개의 정수가 주어진다. 가장 긴 증가하는 부분 수열(LIS)의 길이를 구하라. O(N^2)로는 시간 초과가 발생한다.

입력

첫째 줄에 N, 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다.

• 1 ≤ N ≤ 1,000,000
• -10^9 ≤ 각 수 ≤ 10^9

출력

LIS의 길이를 출력한다.

예제 입력 1

11
3 1 4 1 5 9 2 6 5 3 5

예제 출력 1

4

예제 입력 2

8
10 9 2 5 3 7 101 18

예제 출력 2

4