Descending-Run Sorting

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 a contiguous subsequence whose values strictly decrease from left to right. reverse(slope) reverses the order of the elements in that segment.

You are given a length-N permutation containing each number from 1 through N exactly once. When the initial permutation is partitioned into the minimum number of slopes, every slope has even length. Determine the total number of times reverse is called before the algorithm sorts the permutation in nondecreasing order.

The first line contains an integer N. (2 ≤ N ≤ 100,000)

The second line contains the permutation to sort.

Print the total number of times reverse is called.