题目内容

给定一个排列$p_i$ 。对于其中的一个子段而言，我们称其为错位数组，当且仅当其排序后没有任意一个数在它的原位置上。

现在需要你计算这个排列中有多少个子段是错位数组。

名词解释:

1.排列:$1-n$ 每个数都恰好出现一次。$1\ 3\ 2$ 是一个排列 , $1\ 3\ 4$ 不是一个排列。

2.子段:对于一个数组，删去其开头若干位，删去其结尾若干位所得到的数组。 (有时候我们也叫做子数组)

输入描述

第一行输入一个整数$n (1 \leq n \leq 300)$ 。

第二行输入一个长度为$n$的排列 : $p_1,p_2,...,p_n$

输出描述

输出子段中错位排列的个数。

样例1

输入

2
2 1

输出

1

样例解释

长度为1的子段：都不是错位排列

长度为2的子段：

原数组:$2\ 1$

排序后:$1\ 2$

这是一个错位数组。

所以答案为1

样例2

输入

3
1 2 3

输出

0

由于原序列已经是有序的，所以它的每一个子段也是有序的，所以不存在错位数组。

样例3

输入

5
3 2 1 4 5

输出

2

错位数组分别为:$[1,2],[2,3]$ , 数字代表的是错位数组的左右端点，下标从$1$开始。