正好重新复习一下单调栈，重新写一种不同的写法。

我个人是不太喜欢单调栈边跑边算的，更何况还要记录前一个出栈的就更麻烦了，就写一种不需要边跑边算的做法。

考虑分别跑正的和反的单调栈。正着跑的时候每次找到当前柱子往右第一个大于等于自己的柱子，他们中间能构成一个完整的坑。直到找不到右边不小于自己的为止。显然这只考虑了左边界小于等于右边界，没考虑右边界小于等于左边界的情况。所以还需要反着跑一遍，然后也每次找第一个大于自己的柱子，找出中间构成的坑。之所以反着跑的是大于而不是大于等于，是因为两个边界相等的柱子构成的坑被正着已经跑过一遍了，不能重复计算。

不过我代码里写着是右侧找大于，左侧找大于等于。无所谓，保证不重不漏即可。

int n;
int a[N], s[N], suf[N], pre[N];
int stk[N], sz;
int ans;
int area(int l, int r) { return min(a[l], a[r]) * (r - l - 1) - (s[r - 1] - s[l]); }
int main()
{
    n = rd();
    for (int i = 1; i <= n; ++i)
        a[i] = rd(), s[i] = s[i - 1] + a[i];
    for (int i = 1; i <= n; ++i)
    {
        while (sz && a[stk[sz]] < a[i]) --sz;
        pre[i] = stk[sz], stk[++sz] = i;
    }
    sz = 0;
    for (int i = n; i; --i)
    {
        while (sz && a[stk[sz]] <= a[i]) --sz;
        suf[i] = stk[sz], stk[++sz] = i;
    }    
    int cur = 1;
    while (suf[cur]) ans += area(cur, suf[cur]), cur = suf[cur];
    cur = n;
    while (pre[cur]) ans += area(pre[cur], cur), cur = pre[cur];
    wr(ans);
}