P17720 「FunMusic OI 1C」旋律 / Melody

题目来源：【HT-127-Div.3】核桃CSP-J组模拟赛 &「FunMusic OI R1」 

David 的第三张专辑即将发布，其中有 $n$ 首曲目，每一首曲目都有一个情感值 $p_i$，保证 $p$ 为排列。 David 从专辑中截取连续的一段曲目，当他截取从第 $l$ 首到第 $r$ 首时，他会取出这些曲目的情感值 $[p_l,p_{l+1},\cdots,p_r]$，并把它们从小到大排序。接着，他会将这个排好序的序列划分成若干个连续段，使得每一段内部的数都是连续的正整数。其中最长的那个段，被称为这段曲目的情感线。David 会采取最优的划分方案，使得这个情感线的长度最大，记长度的最大值为 $f(l, r)$。 举个例子，若一段曲目的情感值序列排序后为 $[1,2,5,7,8,9,11]$，其中一种（不是唯一）最优的划分方案为 $[1],[2],[5],[7,8,9],[11]$。因此，其情感线最大长度为 $3$。 David 希望计算对于每段连续的曲目，所产生的情感线长度之和，换句话说，他希望你求出 $\displaystyle \sum_{l = 1} ^ n \sum_{r = l}^ n f(l, r)$ 的值。

第一行一个整数 $n$，表示排列 $p$ 的长度。 第二行 $n$ 个整数，表示 $p_1, p_2, \cdots, p_n$。

输出一行一个整数，表示 $\displaystyle \sum_{l = 1} ^ n \sum_{r = l}^ n f(l, r)$ 的值。

**【样例解释】** - $l=1,r=3$ 时，形成的数值连续段为 $[1,2,3]$，长度最大值为 $3$，即 $f(1, 3) = 3$。 - $l=1,r=2$ 时，形成的数值连续段为 $[1],[3]$，长度最大值为 $1$，即 $f(1, 2)=1$。 - 同理，$f(1, 1)=1$，$f(2,2)=1$，$f(3,3)=1$，$f(2,3)=2$；总和为 $9$。 **【数据范围】** **本题采用捆绑测试。** ::cute-table{tuack} | 子任务编号 | $n\le$ | 特殊性质 | 分值 | | :--------: | :----: | :--------: | :--: | | $1$ | $100$ | 无 | $10$ | | $2$ | $500$ | 无 | $20$ | | $3$ | $3000$ | $\text{A}$ | $10$ | | $4$ | $3000$ | $\text{B}$ | $20$ | | $5$ | $3000$ | 无 | $40$ | 特殊性质 $\text{A}$：对于任意整数 $i\in [1, n]$ 保证 $p_i = i$。 特殊性质 $\text{B}$：保证存在整数 $x\in[0,n)$，使得对于任意 $i\in [1, n]$，都有 $ p_i = ((i + x - 1) \bmod n )+ 1$ 成立。 对于 $100\%$ 的数据，$1\le n\le 3000$，保证 $p$ 为排列。