让我们来考虑从大到小来枚举 C 的最小值 mn。
当 mn 确定时，整个 C 也确定了，对于每个 C_i 只需要取大于等于 mn 且较小的那一个即可。
那么这个 mn 对第 i 个答案造成的贡献就是 \max_{j=1}^i C_j-mn。
然后就得到了一个 O(n^2) 的做法。
上面这个式子又是前缀 max 又要取 min 的，很不好用数据结构来直接维护。
让我们考虑当一个 c_i 被设为 mn 会对前缀 max 造成什么影响。
令 f_i=\max_{j=1}^iC_j。
若 f_{i-1}\ge c_i，那么当 c_i 设为 mn 后，它的值只会变小，对 f 没有影响。
否则 f_{i-1}<c_i，此时 c_i 会被统计到 f 中，那么当 c_i 的值改变后 i 之后的连续一段区间的 f_i 都会改变。
这时，我们只需要对最大值改变的区间来重新统计答案，且其他区间的答案只会变大，所以不用统计。而这部分的贡献又都是 f_{i}-mn，可以用线段树来维护。
不难发现，对于每一个值，在整个过程中至多只会影响一段区间（也可能在之后才更新），所以总的影响次数是 O(n) 的，总时间复杂度 O(n\log n)。