给定一个 $1-N$ 的排列 $P$。
对于一对数字 ${L, R}$ ($1 \le L < R \le n$)，让 $X_{L,R}$ 为 $P_L, P_{L+1}, \dots, P_{R}$ 的第二大值。
请你求出下面式子的值 $$ \sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R} $$
输入格式
第一行一个数字 $N$。
接下来一行 $N$ 个整数 $P_1, P_2, \dots, P_N$。
输出格式
一行一个整数表示 $\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}$ 的值
样例输入
5
1 2 3 4 5样例输出
30数据规模
所有数据保证 $2 \leq N \leq 100000, 1 \leq P_i \leq N, P_i \neq P_j(i \neq j)$。
题外话
如果你用 $n \log n$ 的复杂度通过了本题，你可以思考一下如何更快的通过本题。