Time Limit: 5000 MS Memory Limit: 65536 K

## Description

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 a. The reverse procedure will reverse the
order of the elements in a slope.
You are given a permutation of the first N 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

The first line of input contains the positive integer N (2 ¡Ü N ¡Ü 100 000).
The second line of input contains a permutation of the first N natural numbers that needs to be sorted.
## Output

The only line of output must contain the number of times that reverse is called.
## Sample Input

2
2 1
4
4 3 2 1
4
3 1 4 2
## Sample Output

1
1
3
## Source

coci 2011/2012 contest1