John was given N number of candy bars all of varied length. He puts all the candy bars side by side of each other in a random order and now he wants to arrange them in increasing order of their length, but doesn’t know how to do this in minimum number of attempts. Help him out in doing so.
Input
There will be 2 line of inputs. 1st line will contain number of candies (N) and 2nd line will contain N different heights (positive integer) separated by space.
Output
A single line containing the number of attempts required to arrange the given candies in increasing order of their lengths.
Note :- Shifting and swapping all included into one will be counted as 1 attempt.
Constraints
1 <= N <= 10000
1 <= h <= 10000
In 9 5 4 3 1 7 6 8 10, shifting 10 towards right by one index and then inserting 9 at between 8 and 10 gives 5 4 3 1 7 6 8 9 10 -> 1st attempt now shifting 8, 9 and 10 towards right by one index and then inserting 7 between 6 and 8 gives 5 4 3 1 6 7 8 9 10 -> 2nd attempt doing same for 5 by shifting 6, 7, 8, 9 and 10 towards right and inserting 5 between 1 and 6 gives 4 3 1 5 6 7 8 9 10 ->3rd attempt now shifting 5, 6, 7, 8, 9 and 10 towards right and inserting 4 between 1 and 5 gives 3 1 4 5 6 7 8 9 10 ->4th attempt finally shifting 4, 5, 6, 7, 8, 9 and 10 towards right and inserting 3 between 1 and 4 gives 1 3 4 5 6 7 8 9 10 ->5th attempt
so a total of 5 attempts.
