eolymp
bolt
Try our new interface for solving problems
Problems

Gowk`s Errand for Master

Gowk`s Errand for Master

Time limit 1 second
Memory limit 256 MiB

Do you think that sorting is easy? This is not the case when you're running out of time.

Unexpected weird things often happen in our life. For example, now you have array A and you need to sort it in non-decreasing order. The problem is that you don't really have time to do that.

Fortunately, your friend is very good at sorting arrays, so you decided to ask for his help. You believe that your friend's special abilities are due to his very conceptual approach. In one second he takes an element out of the array and places it either at the beginning or the end of the array.

For example, if the array is 4 2 5 6 1 3, then taking out 5 and placing it at the beginning would yield 5 4 2 6 1 3, while taking out 2 and placing it at the end would yield 4 5 6 1 3 2.

Of course, your friend does everything as fast as possible, because he doesn't want to waste his time. The only thing you want to know is how much time you have for doing other useful things while your array is being sorted.

Input data

The first line contains N (1N310^5) - the number of elements in A. The second line contains N integer numbers A_i (1A_i10^6)

Output data

Print the sought minimum time needed for your friend to sort A, in seconds.

Examples

Input example #1
5
2 5 1 3 3
Output example #1
2
Author Gennady Korotkevich
Source Gennady Korotkevich Contest 1, Petrozavodsk Training Camp, Day 1, Friday, August 23, 2013