[ABC140E] Second Sum
题意翻译
给定一个N的排列P,对于区间[l, r],其中l < r,求所有区间[l, r]中第二大的数的和。
题目描述
[problemUrl]: https://atcoder.jp/contests/abc140/tasks/abc140_e
$ \{1,\ 2,\ \ldots,\ N\} $ の順列 $ P $ が与えられます。
ペア $ (L,\ R)\ (1\ \le\ L\ \lt\ R\ \le\ N) $について、$ P_L,\ P_{L+1},\ \ldots,\ P_R $ の中で $ 2 $ 番目に大きいものを $ X_{L,\ R} $ とします。
$ \displaystyle\ \sum_{L=1}^{N-1}\ \sum_{R=L+1}^{N}\ X_{L,R} $ を求めてください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ P_1 $ $ P_2 $ $ \ldots $ $ P_N $
输出格式
$ \displaystyle\ \sum_{L=1}^{N-1}\ \sum_{R=L+1}^{N}\ X_{L,R} $ を出力せよ。
输入输出样例
输入样例 #1
3
2 3 1
输出样例 #1
5
输入样例 #2
5
1 2 3 4 5
输出样例 #2
30
输入样例 #3
8
8 2 7 3 4 5 6 1
输出样例 #3
136
说明
### 制約
- $ 2\ \le\ N\ \le\ 10^5 $
- $ 1\ \le\ P_i\ \le\ N $
- $ P_i\ \neq\ P_j $ $ (i\ \neq\ j) $
- 入力はすべて整数
### Sample Explanation 1
$ X_{1,\ 2}\ =\ 2,\ X_{1,\ 3}\ =\ 2,\ X_{2,\ 3}\ =\ 1 $ より、総和は $ 2\ +\ 2\ +\ 1\ =\ 5 $ となります。