Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.
Since the answer may be large, return the answer modulo 10^9 + 7.
Example 1:
Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.
Note:
1 <= A.length <= 30000
1 <= A[i] <= 30000
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left = [0] * n
        right = [0] * n
        s = []
        
        for i in range(n):
            count = 1
            while s and s[-1][0] >= A[i]:
                count += s.pop()[1]
            left[i] = count
            s.append((A[i], count))
        s = []
        for i in range(n-1, -1, -1):
            count = 1
            while s and s[-1][0] > A[i]:
                count += s.pop()[1]
            right[i] = count
            s.append((A[i], count))
        print(left)
        print(right)
        s = 0
        for i in range(n):
            s += (left[i]) * (right[i]) * A[i]
        return s % (10 **9 + 7)
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left = [0] * n
        right = [0] * n
        s = []
        
        for i in range(n):
            count = 1
            while s and s[-1][0] >= A[i]:
                count += s.pop()[1]
            left[i] = count
            s.append((A[i], count))
        s = []
        for i in range(n-1, -1, -1):
            count = 1
            while s and s[-1][0] > A[i]:
                count += s.pop()[1]
            right[i] = count
            s.append((A[i], count))
        print(left)
        print(right)
        s = 0
        for i in range(n):
            s += (left[i]) * (right[i]) * A[i]
        return s % (10 **9 + 7)