408676: GYM103261 C StalinSort Algorithm

Memory Limit:0 MB Time Limit:3 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. StalinSort Algorithmtime limit per test3 secondsmemory limit per test512 mebibytesinputstandard inputoutputstandard output

There is an esoteric sorting algorithm called StalinSort. It goes as follows.

Go through the elements of the given array from left to right, starting from the second. If the current element is not less than previous, then do nothing, otherwise erase it. In the end you get a sorted array.

One can implement StalinSort in $$$O(n)$$$ time, which is pretty cool. There is a catch though: you can lose many elements in the process. To fix this I've come up with an improved nondeterministic version of this algorithm.

Go through the elements of the given array from left to right, starting from the second. If the current element is not less than previous, then do nothing, otherwise you have options. You can either erase it, or erase the previous element, but only if the current prefix still becomes non-decreasing. In the end you get a sorted array.

Depending on its choices, this algorithm can erase different number of elements. I wonder, what is the minimum number of erased elements I can get applying this improved version of StalinSort to the given permutation?

Input

The first line contains one positive integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — the size of the permutation.

The second line contains $$$n$$$ integers $$$p_{i}$$$ ($$$1 \le p_{i} \le n$$$) — the permutation itself. It is guaranteed that all $$$p_{i}$$$ are distinct.

Output

Print one number — the minimum number of elements improved StalinSort can erase.

ExamplesInput
6
6 1 2 3 4 5
Output
1
Input
6
5 6 1 2 3 4
Output
4
Input
6
6 4 5 1 2 3
Output
3

加入题单

上一题 下一题 算法标签: