第二大数

题号：NC232580
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

牛神对于第一的宝座感到厌倦，他开始研究第二大的贡献。
现在给你一个 $N$ 个数的排列 $P$ ,包含 $(1,2,...,N)$ ，其中对于任给的一组 $(L,R)$ $( 1 \le L<R \le N)$ ，定义 $X_{L,R}$ 为序列元素从下标 $L$ 到 $R$ 中第二大的数。
现在请聪明的你算出 $\sum_{L=1}^{N-1}\sum_{R=L+1}^NX_{L,R}$ 的结果，AC者可凭运气获得牛神签名照一张。

输入描述:

第一行为牛神想要研究的数字 $N$ ，其中 $2 \le N \le10^{4}$ 。
第二行为 $N$ 的一个排列。

输出描述:

输出包括一个整数，表示所求结果。

示例1

输入

复制

3
2 3 1

输出

复制