不妨分开计算，前一部分记为$Ap_1$
$p_1$产生的贡献次数就是$[l,r]$中满足区间端点是最大、次大值的区间个数。
不妨枚举次次大值（当然要考虑不存在的情况）
$$A=r-l+\sum_{l\le i< j\le r}[\max_{i<x<j}k_x<k_i][\max_{i<x<j}k_x<k_j]=r-l+\sum_{l<x<r}\sum_{l\le i<x}\sum_{x<j\le r}[k_x<k_i][k_x<k_j][\max_{i<y<j}k_y=k_x]$$
我们假设$M_x$为包含$x$且最大值为$k_x$的最长区间
于是
$$A=r-l+\sum_{l<x<r}\sum_{l\le i<x}\sum_{x<k\le r}[k_x<k_i][k_x<k_j][[i+1,j-1]\subset M_x]$$
显然，假如$[i+1,j-1]\not= M_x$，假如$[i,j-1]\subset x$于是$[k_x<k_i]=0$，假如$[i+1,j]\subset x$于是$[k_x<k_j]=0$
于是
$$[[i+1,j-1]=M_x]=[k_x<k_i][k_x<k_j][[i+1,j-1]\subset M_x]$$
所以
$$A=r-l+\sum_{l<x<r}\sum_{l\le i<x}\sum_{x<k\le r}[[i+1,j-1]=M_x]=r-l+\sum_{l<x<r}[M_x\subset[l+1,r-1]]$$
by huhao @ 2019-02-15 14:23:42
@[Owen_codeisking](/space/show?uid=35069) 从我（还没发）的博客里copy出来的
by huhao @ 2019-02-15 14:24:40
@[huhao](/space/show?uid=19410) 谢谢
by Owen_codeisking @ 2019-02-15 17:08:48
@[Owen_codeisking](/space/show?uid=35069)
其实有个简单一点的理解方式...
考虑枚举中间的位置（即题目里的$c$），我们发现每个$c$只会产生最多一次贡献，即左右端点为第一个大于$c$的元素的区间。所以总的区间个数不超过$n$
by suwakow @ 2019-06-24 06:58:09
@[suwakow](/user/102506)
那如果所有数都相等呢？那岂不是n*(n-1)/2个？
by loadingyy @ 2021-08-08 20:45:31
@[loadingyy](/user/30296) 但是题目里给出了限制：灵魂的战斗力组成一个 1 到 n 的排列，因此本题中不会重复
by 入户功夫 @ 2021-09-16 20:01:32