第二大数字和

题目描述

给定一个 $1-N$ 的排列 $P$。

对于一对数字 ${L, R}$ ($1 \le L < R \le n$)，让 $X_{L,R}$ 为 $P_L, P_{L+1}, \dots, P_{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$ 的复杂度通过了本题，你可以思考一下如何更快的通过本题。