문제 169
가장 긴 증가하는 부분 수열
길이가 $N$인 정수 수열 $A_1, A_2, \cdots, A_N$이 주어진다.
원소를 일부 선택하여 원래 순서를 유지한 수열을 부분 수열이라고 한다. 원소가 엄격히 증가하는 부분 수열의 길이의 최댓값을 구해 보자.
입력
첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 200\,000)$
두 번째 줄에 수열의 원소 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \le A_i \le 10^9)$
출력
엄격히 증가하는 부분 수열의 길이의 최댓값을 출력한다.
예제 입력 1
6 10 20 10 30 20 50
예제 출력 1
4
예제 입력 2
4 7 7 7 7
예제 출력 2
1
예제 입력 3
5 -3 -2 -5 0 1
예제 출력 3
4