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

수열 $A$가 주어졌을 때, 가장 긴 증가하는 부분 수열의 길이를 구하는 프로그램을 작성하시오.

부분 수열은 $A$에서 원소를 0개 이상 지우고 남은 원소를 원래 순서대로 이어 붙인 수열이다. 증가하는 부분 수열은 앞에 있는 원소가 바로 뒤에 있는 원소보다 항상 작은 부분 수열이다. 값이 같은 두 원소는 한 부분 수열에 나란히 놓을 수 없다.

예를 들어 $A = \{10, 20, 10, 30, 20, 50\}$이면 가장 긴 증가하는 부분 수열은 $\{10, 20, 30, 50\}$이고 길이는 $4$이다.

첫째 줄에 수열 $A$의 크기 $N$이 주어진다. ($1 \le N \le 1\,000\,000$)

둘째 줄에 수열 $A$를 이루는 $A_1, A_2, \dots, A_N$이 공백 하나로 구분되어 주어진다. ($1 \le A_i \le 1\,000\,000$)

첫째 줄에 수열 $A$의 가장 긴 증가하는 부분 수열의 길이를 출력한다.