시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB32141445.161%

문제

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$.

예제 입력 1

3
2 1 3

예제 출력 1

2

예제 입력 2

4
4 3 2 1

예제 출력 2

0

예제 입력 3

4
2 1 4 3

예제 출력 3

2

예제 입력 4

6
4 6 5 2 1 3

예제 출력 4

4

예제 입력 5

4
3 4 1 2

예제 출력 5

2