candy-bars-2

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

SAMPLE INPUT
9
9 5 4 3 1 7 6  8 10

SAMPLE OUTPUT
5

Explanation

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.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: