Cannot parse: 1ss error parsing time
给定一个 1−N 的排列 P。
对于一对数字 L,R (1≤L<R≤n),让 XL,R 为 PL,PL+1,…,PR 的第二大值。
请你求出下面式子的值
L=1∑N−1R=L+1∑NXL,R
输入格式
第一行一个数字 N。
接下来一行 N 个整数 P1,P2,…,PN。
输出格式
一行一个整数表示 ∑L=1N−1∑R=L+1NXL,R 的值
样例输入
5
1 2 3 4 5
样例输出
30
数据规模
所有数据保证 2≤N≤100000,1≤Pi≤N,Pi=Pj(i=j)。
题外话
如果你用 nlogn 的复杂度通过了本题,你可以思考一下如何更快的通过本题。