Consider the following sorting algorithm:
reverse-sort(sequence a)
while (a is not in nondecreasing order)
partition a into the minimum number of slopes
for every slope with length greater than one
reverse(slope)
A slope is defined as a decreasing consecutive subsequence of . The reverse procedure will reverse the order of the elements in a slope.
You are given a permutation of the first natural numbers whose slopes all have even length when partitioned for the first time. Determine the total number of times reverse is called to reverse-sort the given permutation.
Input Specification
The first line of input contains the positive integer .
The second line of input contains a permutation of the first natural numbers that needs to be sorted.
Output Specification
The only line of output must contain the number of times that reverse is called.
Sample Input 1
2
2 1
Sample Output 1
1
Sample Input 2
4
4 3 2 1
Sample Output 2
1
Sample Input 3
4
3 1 4 2
Sample Output 3
3
Comments