1
class Solution:
2
    def sumSubarrayMins(self, arr: List[int]) -> int:
3
        n = len(arr)
4
        small_before = [-1] * n
5
        stack = []
6
        for i in range(n):
7
            while stack and arr[stack[-1]] >= arr[i]:
8
                stack.pop()
9
            if stack:
10
                small_before[i] = stack[-1]
11
            stack.append(i)
12
        best = [0] * (n + 1)
13
        ans = 0
14
        for i in range(n):
15
            best[i] = best[small_before[i]] + (i - small_before[i]) * arr[i]
16
            ans += best[i]
17
        return ans % 1000000007