题目描述

考虑如下的排序算法：

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)

定义 slope 为 a 的递减子串，reverse() 将翻转一段序列。

给定一个 $1$ ~ $N$ 的排列，保证在第一次划分时每个 slope 的长度都为偶数，求如果使用这种排序算法对给定的排列进行排序，需要调用多少次 reverse(slope)。

输入格式

输入的第一行包含一个正整数 $N$。

第二行包含 $N$ 个互不相同的的正整数，代表待排序的排列。

输出格式

输出一行一个整数，表示 reverse(slope) 需要被调用的次数。

2
2 1

1

4
4 3 2 1

1

4
3 1 4 2

3

提示

【数据范围】

对于 $100\%$ 的数据，$2 \le N \le 10^5$。

【说明】

本题分值按 COCI 原题设置，满分 $140$。

题目译自 COCI2011-2012 CONTEST #1 T5 SORT。