LC364 T3

using ll = long long;
class Solution {
public:
    long long maximumSumOfHeights(vector<int>& mh) {
        ll ret = 0;
        int n = mh.size();
        vector<ll> pref(n), suff(n);
        stack<int> stck;
        for (int i = 0; i < n; ++i) {
            while(stck.size() && mh[i] < mh[stck.top()]) stck.pop();
            if (stck.size() == 0) pref[i] = ll(i + 1) * mh[i];
            else pref[i] = ll(i - stck.top()) * mh[i] + pref[stck.top()];
            stck.push(i);
        }
        while(stck.size()) stck.pop();
        for (int i = n - 1; i >= 0; --i) {
            while(stck.size() && mh[i] < mh[stck.top()]) stck.pop();
            if (stck.size() == 0) suff[i] = ll(n - i) * mh[i];
            else suff[i] = ll(stck.top() - i) * mh[i] + suff[stck.top()];
            stck.push(i);
        }

        for (int i = 0; i < n; ++i) {
            ret = max(ret, suff[i] + pref[i] - mh[i]);
        }
        return ret;
    }
};