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

Given a permutation of numbers from $1$ to $N$, where each slope has an even length during the first partition, determine the number of times reverse(slope) needs to be called to sort the given permutation using this algorithm.

Input Format

The first line of input contains a positive integer $N$.

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

Output Format

Output a single integer, which is the number of times reverse(slope) needs to be called.

Sample Input and Output

Sample Input #1

2
2 1

Sample Output #1

1

Sample Input #2

4
4 3 2 1

Sample Output #2

1

Sample Input #3

4
3 1 4 2

Sample Output #3

3

Notes

Data Range

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

Notes

This problem's score is set according to the original COCI contest, with a maximum score of $140$.

The problem is translated from COCI2011-2012 CONTEST #1 T5 SORT.

见题面 Input 部分

见题面 Output 部分