Descending-Run Sorting

Time limit1sMemory limit128 MB

Summary

Given a permutation whose minimal slope decomposition always has even-length decreasing runs, simulate/derive how many reversal operations the described repeated slope-reversal sort performs until the array is sorted.

Level: Medium7 of 10
Topics: Array, Simulation, Math
Solved: No attempts yet

Problem

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.

Input

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

The second line contains the permutation to sort.

Output

Print the total number of times reverse is called.

Examples3

Example 1
Input
```
2
2 1
```
Expected output
```
1
```
Example 2
Input
```
4
4 3 2 1
```
Expected output
```
1
```
Example 3
Input
```
4
3 1 4 2
```
Expected output
```
3
```