题目描述

给出一个由$\{1,\ 2,\ \ldots,\ N\}$ 组成的排列 $P$

对于一对 $(L,\ R)\ (1\ \le\ L\ \lt\ R\ \le\ N)$记 $X_{L,R}$ 为$P_L,\ P_{L+1},\ \ldots,\ P_R$ 中的第二大的数值。

找出$\displaystyle\ \sum_{L=1}^{N-1}\ \sum_{R=L+1}^{N}\ X_{L,R}$ 。

输入

第一行一个整数$N$

第二行$N$个整数，表示排列

输出

输出$\displaystyle\ \sum_{L=1}^{N-1}\ \sum_{R=L+1}^{N}\ X_{L,R}$

3
2 3 1

5

样例解释1

$X_{1,2}$=2,$X_{1,3}$=2，并且$X_{2,3}=1，所以和为2+2+1= 5.$

5
1 2 3 4 5

30

8
8 2 7 3 4 5 6 1

136

提示

• $2\ \le\ N\ \le\ 10^5$
• $1\ \le\ P_i\ \le\ N$
• $P_i\ \neq\ P_j$ $(i\ \neq\ j)$