Reverse Sort Reversal Count

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)

Here, a slope is defined as a maximal consecutive strictly decreasing subsequence of a, and reverse() reverses the order of a segment in the sequence.

You are given a permutation of the integers from \(1\) to \(N\). It is guaranteed that in the first partition all slopes have even lengths. Your task is to compute the total number of times the reverse(slope) operation is called when sorting the permutation using the above algorithm.

Note: The algorithm works as follows. In each iteration, partition the current sequence into the minimum number of slopes. For every slope that contains more than one element, reverse that entire slope (which counts as one reversal). Continue this process until the sequence is sorted in nondecreasing order.

inputFormat

The first line contains an integer \(N\) representing the size of the permutation. The second line contains \(N\) space-separated integers representing a permutation of \(1, 2, \dots, N\).

outputFormat

Output a single integer: the total number of times the reverse(slope) operation is called to sort the permutation.

sample

2
2 1

1