시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 32 | 14 | 14 | 45.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$.
3 2 1 3
2
4 4 3 2 1
0
4 2 1 4 3
2
6 4 6 5 2 1 3
4
4 3 4 1 2
2