题目内容

魔法师塔子哥手上有一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$，保证序列里每个元素不重复且$1 <= a[i] <= n$，他想要知道有多少个区间 $[l, r]$ 满足区间内部的数 $a_{l}, a_{l+1}, \ldots, a_{r}$ 能够构成一个排列。

为了更好地掌握魔法，塔子哥需要知道所有满足条件的区间数量。现在他请你来帮助他计算这个数量。

思路

排列其实就是一个数组$n$个数，包好$1$到$n$各一位。所以我们可以将数组排序，将数组排序后，我们会得到一个$1$到$n$的数组，同时我们用$pos[i]$表示一个数$i$在原数组的位置。

我们拿样例$[2,1,5,3,4]$来讲解。

那么我们得到的$pos$数组是$[2,1,4,5,3]$。

我们将数字和$pos$绑定为二元组。所以原数组为$[(2,1),(1,2),(5,3),(3,4),(4,5)]$（二元组第一位表示数字，第二位表示位置）。我们排序后，数组变为$[(1,2),(2,1),(3,4),(4,5),(5,3)]$。