Help DJ :
Difficulty Level : Easy
Submissions : 103
Asked In :
Marks :10
: 0 | : 0
DJ Varun works in a club and plays cool songs. He has $$$N$$$ disks of different albums (each of equal radius). Every disk has a distinct number out of $$$1$$$ to $$$N$$$ associated with it. Disks are placed one over the other in a single pile. Varun wants to sort this pile of disks in an increasing order i.e., top to bottom. But he has a very special method of doing this. In a single step, he can only choose one disk out of the pile and he can only put it at the top. So the task here is that Varun wants to sort his pile of disks in a minimum number of possible steps. What is the minimum number of possible steps to sort the pile so that Varun can check whether he is doing his work right or wrong?
The first line contains integer N, the size of the array, followed by an array of size N containing integers 1 to N in any random order, which shows the position of disks from top to bottom.
$$$1 \le N \le 10^6$$$
Print the Minimum number of steps needed to sort the pile. If it can't be sorted, then return the output as -1.
5 5 4 3 2 1
0
5 1 2 3 4 5
4
5 1 5 3 4 2
3
