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

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

부분 수열은 $A$에서 원소를 몇 개 골라 원래 순서대로 늘어놓은 수열이다. 증가하는 부분 수열은 앞에서 뒤로 갈수록 값이 항상 커지는 부분 수열이고, 같은 값이 두 번 들어가면 증가하지 않는다.

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

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

둘째 줄에 수열 $A$를 이루는 정수 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($-10^9 \le A_i \le 10^9$)

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