问题 BK: Bob和Alice(5)
内存限制:128 MB
时间限制:2.000 S
评测方式:文本比较
命题人:
提交:73
解决:14
题目描述
Bob和Alice最近对序列真的着迷了
他们又提出了个序列游戏
有一个1到n的随机排列P
$P_1$ $P_2$ .......$P_n$
并且定义$X_{l,r}$为[l,r]这个区间内$P$的第二大值即{$P_l$ , $P_{l+1}$ ,.......,$P_r$}中第二大的
1 <= l < r <= n
求$\sum_{l=1}^{n-1}$ $\sum_{r=l+1}^{n}{X_{l,r}}$
他们又提出了个序列游戏
有一个1到n的随机排列P
$P_1$ $P_2$ .......$P_n$
并且定义$X_{l,r}$为[l,r]这个区间内$P$的第二大值即{$P_l$ , $P_{l+1}$ ,.......,$P_r$}中第二大的
1 <= l < r <= n
求$\sum_{l=1}^{n-1}$ $\sum_{r=l+1}^{n}{X_{l,r}}$
输入
n
$P_1$ $P_2$ .......$P_n$
2 <= n <= 105
$P_1$ $P_2$ .......$P_n$
2 <= n <= 105
输出
求$\sum_{l=1}^{n-1}$ $\sum_{r=l+1}^{n}{X_{l,r}}$
样例输入 复制
3
2 3 1
样例输出 复制
5
提示
$X_{1,2}$ = 2 , $X_{1,3}$ = 2 , $X_{2,3}$ = 1
所以答案 = 1 + 2 + 1
所以答案 = 1 + 2 + 1