Maximal Subsequence

아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제 설명

예제5

문제

Let the beauty of a sequence be the length of its longest increasing subsequence.

You are given an array $a$ consisting of $n$ integers. Find the maximum length of a subsequence of array $a$ such that the beauty of this subsequence is less than the beauty of the whole array $a$ .

입력

The first line contains a single integer $n$ , the number of elements in array $a$ ( $1 \le n \le 5 \cdot 10^5$ ).

The second line contains $n$ space-separated integers $a\_1, a\_2, \ldots, a\_n$ ( $1 \le a\_i \le 10^9$ ).

출력

Print one integer: the maximum length of a subsequence of array $a$ such that its beauty is less than the beauty of the whole array $a$ .