최대 부분수열

시간 제한1초메모리 제한256 MB

요약

배열이 주어졌을 때 전체 배열의 LIS 길이보다 LIS가 짧은 부분 수열 중 가장 긴 것의 길이를 구합니다.

문제

어떤 수열의 아름다움은 그 수열의 가장 긴 증가 부분수열의 길이이다.

길이가 $n$ 인 배열 $a$ 가 주어진다. 배열 $a$ 의 부분수열 가운데 그 부분수열의 아름다움이 배열 $a$ 전체의 아름다움보다 작은 것의 최대 길이를 구하라.

첫째 줄에 배열 $a$ 의 원소 개수 $n$ 이 주어진다 ( $1 \le n \le 5 \cdot 10^5$ ).

둘째 줄에 공백으로 구분된 정수 $a_1, a_2, \ldots, a_n$ 이 주어진다 ( $1 \le a_i \le 10^9$ ).

아름다움이 배열 $a$ 전체의 아름다움보다 작은 부분수열의 길이 중 최댓값을 정수 하나로 출력한다.