Old Huseyn
At just 17 years old, Guseyn feels like an old man and believes it's time for him to leave Computer Science. Therefore, he must complete all his important projects and experiments. He has almost finished all his projects and experiments, with only one remaining. He had a wonderful sorted array, but after numerous experiments, something unforeseen happened: the array was no longer sorted! It might seem simple to sort an array, but Guseyn decided to conduct one more experiment. He wants to sort the array using only two operations:
Take any element of the array and move it to the end of the array.
Take any element of the array and move it to the beginning of the array.
Thus, if the array initially contained elements a[1], a[2], ..., a[i-1], a[i], a[i+1], ..., a[n] and the i-th element was chosen, then if the first operation is applied, the array becomes a[1], a[2], ..., a[i-1], a[i+1], ..., a[n], a[i]. In the case of applying the second operation, it becomes a[i], a[1], a[2], ..., a[i-1], a[i+1], ..., a[n]. It turned out that with these two operations, the array can always be sorted, which Guseyn did with his array. But now Guseyn has given you a new array and asked you to find the minimum number of such operations needed to sort the new array.
Input
The first line contains a single integer n – the length of the array given to you by Guseyn (1 <= n <= 300000).
The second line contains n integers a[i] separated by spaces – the elements of the array (1 <= a[i] <= 10^9).
Output
Output a single number – the minimum number of operations needed to apply to the given array to make it sorted.