思路：以右端点从左到右扫描线。

设$w(l, r)=\min \limits_{i=l}^r a_i$，维护一个数组$b$，对于目前右端点$r$，$b_i=w(i, r)$

对于$r$找到前面最近的满足$a_p\leq a_r$的点$p$，将$b[p + 1...r]$改为$a_r$，然后维护一个序列$c$使得所有的$c_x$都加上$b_x$。

对于每个左端点$l$计算$c[l...r]$的和。