题目描述
给定一个排列P,其中P是由1,2,ldots,N组成的。
对于一对(L,R)(1leLltRleN),令XL,R表示PL,PL+1,ldots,PR中第二大的值。
求displaystylesumL=1N−1sumR=L+1NXL,R的值。
约束条件
- 2leNle105
- 1lePileN
- PineqPj (ineqj)
- 输入中的所有值都是整数。
输入格式
输入以以下格式从标准输入给出:
N
P1 P2 ldots PN
输出格式
打印displaystylesumL=1N−1sumR=L+1NXL,R的值。
示例输入1
示例输出1
X1,2=2,X1,3=2,X2,3=1,所以和为2+2+1=5。
示例输入2
示例输出2
示例输入3
示例输出3