907. 子数组的最小值之和（贡献法，单调栈，前后缀分解）

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10 ** 9 + 7
        n = len(arr)
        pre = [-1] * n
        suf = [n] * n
        stk = []

        for i in range(n):
            while stk and arr[stk[-1]] >= arr[i]:
                stk.pop()
            if stk:
                pre[i] = stk[-1]
            stk.append(i)

        stk.clear()

        for i in range(n - 1, -1, -1):
            while stk and arr[stk[-1]] > arr[i]:
                stk.pop()
            if stk:
                suf[i] = stk[-1]
            stk.append(i)

        return sum((i - pre[i]) * (suf[i] - i) * v for i, v in enumerate(arr)) % MOD