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 contiguous subsequence of a, and reverse() reverses a segment of the sequence.

You are given a permutation of $1$ to $N$. It is guaranteed that, in the first partition, the length of every slope is even. Determine how many times reverse(slope) will be called if this sorting algorithm is used to sort the given permutation.

Input Format

The first line contains a positive integer $N$.

The second line contains $N$ distinct positive integers, representing the permutation to be sorted.

Output Format

Output one integer on a single line, the number of times reverse(slope) needs to be called.

2
2 1

1

4
4 3 2 1

1

4
3 1 4 2

3

Hint

Constraints

For $100\%$ of the testdata, $2 \le N \le 10^5$.

Explanation

The score of this problem follows the original COCI settings, with a full score of $140$.

Translated from COCI2011-2012 CONTEST #1 T5 SORT.

Translated by ChatGPT 5