Maximal Subsequence

Time limit1sMemory limit256 MB

Summary

Given an array, find the longest subsequence whose LIS length is strictly smaller than the LIS length of the whole array.

Level: Medium7 of 10
Topics: Dynamic programming, Binary search, Graph
Solved: No attempts yet

Problem

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

Input

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

Output

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

Examples5

Example 1
Input
```
3
2 1 3
```
Expected output
```
2
```
Example 2
Input
```
4
4 3 2 1
```
Expected output
```
0
```
Example 3
Input
```
4
2 1 4 3
```
Expected output
```
2
```
Example 4
Input
```
6
4 6 5 2 1 3
```
Expected output
```
4
```
Example 5
Input
```
4
3 4 1 2
```
Expected output
```
2
```