#3176. [Coci 2012]Sort

内存限制:32 MiB 时间限制:1 Sec

题目描述

有一种排序算法,称为reverse-sort算法。这个算法的过程是这样的,每次将
给出的序列划分为尽量少的连续部分,使得每一部分都是单调递减的序列。然后将
每一个不少于两个数组成的部分reverse(即翻转),重复上述操作,直到序列单
调不下降。现在给出1..n的一个排列,排列满足最初划分得到的各个部分的长度都是偶
数。对这个序列执行reverse-sort算法。求算法执行过程中reverse操作共进行了
多少次。
n <= 100,000.

输入格式

第一行一个数字N

第二行N个数字,为1到N某个排列

输出格式

如题所述

样例

样例输入


			
4
3 1 4 2

样例输出


			
3

数据范围与提示