背景

题目来源：【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)$ 的值。

3
1 3 2

9

2
1 2

4

提示

【样例解释】

• $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$ 为排列。