Sum of Second Largests

Problem Description

You are given a permutation $P$ of $1, 2, \dots, N$.

For a pair of indices $\{L, R\}$ ($1 \le L < R \le N$), let $X_{L,R}$ be the second largest value among $P_L, P_{L+1}, \dots, P_R$.

Compute the following sum:

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $P_1, P_2, \dots, P_N$.

Output Format

Output one line containing a single integer: the value of $\sum_{L=1}^{N-1} \sum_{R=L+1}^{N} X_{L,R}$.

Sample Input

5
1 2 3 4 5

Sample Output

30

Constraints

$2 \le N \le 100000$, $1 \le P_i \le N$, and $P_i \neq P_j$ for $i \neq j$.

Hint

If you passed this problem in $O(n \log n)$, try to think of a faster solution.