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

Difficulty: interview

Starter code:

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        stack = []
        result = 0
        A = [0] + A + [0]

        for i, x in enumerate(A):
            while stack and x < A[stack[-1]]:
                j = stack.pop()
                result += A[j] * (i - j) * (j - stack[-1])
            stack.append(i)

        return result % (10**9 + 7)


class Solution:
    def sumSubarrayMins(self, A):
        res = 0
        s = []
        A = [0] + A + [0]
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        MOD = 10**9 + 7
        N = len(A)

        # prev has i* - 1 in increasing order of A[i* - 1]
        # where i* is the answer to query j
        stack = []
        prev = [None] * N
        for i in range(N):
            while stack and A[i] < A[stack[-1]]:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)

        # next has k* + 1 in increasing order of A[k* + 1]
        # where k* is the answer to query j
        stack = []
        next_ = [None] * N
        for k in range(N-1, -1, -1):
            while stack and A[k] <= A[stack[-1]]:
                stack.pop()
            next_[k] = stack[-1] if stack else N
            stack.append(k)

        # Use prev/next array to count answer
        return sum((i - prev[i]) * (next_[i] - i) * A[i]
                   for i in range(N)) % MOD
            
                    
                


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # build previous less element array
        previous_less = [-1] * len(A)
        p_stack = []
        
        # build next less element array
        next_less = [len(A)] * len(A)
        n_stack = []
        
        for i in range(len(A)):
            n = A[i]
            # remove larger until find the smaller one
            while p_stack and A[p_stack[-1]] > n:
                p_stack.pop()
            # stack top is previous less of A[i]
            # if empty, record -1, else record stack top index
            if p_stack:
                previous_less[i] = p_stack[-1]
            else:
                previous_less[i] = -1
            p_stack.append(i)
            
            # remove larger until find the smaller one
            while n_stack and A[n_stack[-1]] > n:
                # index of the one need to be updated
                # the one that is bigger than A[i]
                x = n_stack[-1]
                n_stack.pop()
                next_less[x] = i
            n_stack.append(i)
            
        #print(previous_less)
        #print(next_less)
        
        ans = 0
        mod = 10 ** 9 + 7
        for i in range(len(A)):
            # calculate distance to left and right
            left = i - previous_less[i]
            right = next_less[i] - i
            #print(left)
            #print(right)
            
            ans = (ans + A[i] * left * right) % mod
        return ans

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        low = [None] * (n)
        high = [None] * (n)
        stack = []
        
        for i in range(n):
            while stack and A[stack[-1]] >= A[i]:
                stack.pop()
            
            low[i] = stack[-1] if stack else -1
            stack.append(i)
        
        stack = []
        for i in range(n-1, -1, -1):
            while stack and A[stack[-1]] > A[i]:
                stack.pop()
            high[i] = stack[-1] if stack else n
            stack.append(i)
        ans = 0
        for i in range(n):
            ans = (ans + (i - low[i]) * (high[i] - i) * A[i]) % int(1e9 + 7)
        return ans


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        left = [0]*len(A)
        right = [0]*len(A)
        s1, s2 = [], []
        for i in range(len(A)):
            count = 1
            while s1 and s1[-1][0]>A[i]:
                count+=s1.pop()[1]
            s1.append([A[i],count])
            left[i]=count
        for i in range(len(A))[::-1]:
            count = 1
            while s2 and s2[-1][0]>=A[i]:
                count+=s2.pop()[1]
            s2.append([A[i],count])
            right[i]=count
        ret = 0
        for i in range(len(A)):
            ret+=A[i]*(left[i]*right[i])
        return ret%(10**9+7)
                
            
                


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        firstLessR = []
        firstLessL = []
        
        n = len(A)
        for i in range(n):
            firstLessR.append(i)
            firstLessL.append(i)
        
        incNums = []
        
        for i in range(n):
            if i == 0:
                incNums.append(i)
            else:
                while len(incNums) > 0 and A[incNums[-1]] >= A[i]:
                    firstLessR[incNums[-1]] = i
                    incNums.pop()
                incNums.append(i)
        
        for i in incNums:
            firstLessR[i] = n
        
        incNums = []
        for i in range(n-1, -1, -1):
            if i == n-1:
                incNums.append(i)
            else:
                while len(incNums) > 0 and A[incNums[-1]] > A[i]:
                    firstLessL[incNums[-1]] = i
                    incNums.pop()
                incNums.append(i)
        
        for i in incNums:
            firstLessL[i] = -1
        ans = 0
        #print(firstLessR, firstLessL)
        for i in range(n):
            w = (firstLessR[i] - i) * (i - firstLessL[i])
            ans += w * A[i]
            ans = ans % 1000000007
        
        return ans

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        count = [0] * n
        s = []
        for i in range(n):
            while len(s)>0 and A[i] <= A[s[-1]]:
                s.pop()
            if len(s) == 0:
                count[i] = i+1
            else:
                count[i] = i-s[-1]
            s.append(i)
        s = []
        for i in range(n-1,-1,-1):
            while len(s)>0 and A[i] < A[s[-1]]:
                s.pop()
            if len(s) == 0:
                count[i] *= (n-i)
            else:
                count[i] *= (s[-1]-i)
            s.append(i)
        res = 0
        for i in range(n):
            res += count[i]*A[i]
        return res%1000000007

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        MOD = 10**9 + 7
        stack = []
        ans = dot = 0
        for j, y in enumerate(A):
            count = 1
            while stack and stack[-1][0] >= y:
                x, c = stack.pop()
                count += c
                dot -= x * c
            stack.append((y, count))
            dot += y * count
            ans += dot
            
        return ans % MOD


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # Prev/Next Array
        # Time  complexity: O(N)
        # Space complexity: O(N)
        MOD = 10**9 + 7
        N = len(A)

        # prev has i* - 1 in increasing order of A[i* - 1]
        # where i* is the answer to query j
        stack, prev = [], [None] * N
        for i in range(N):
            while stack and A[i] <= A[stack[-1]]:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)

        # next has k* + 1 in increasing order of A[k* + 1]
        # where k* is the answer to query j
        stack = []
        next_ = [None] * N
        for k in range(N - 1, -1, -1):
            while stack and A[k] < A[stack[-1]]:
                stack.pop()
            next_[k] = stack[-1] if stack else N
            stack.append(k)

        # Use prev/next array to count answer
        return sum((i - prev[i]) * (next_[i] - i) * A[i] for i in range(N)) % MOD



class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left, right, sl, sr = [0] * n, [0] * n, [], []
        # left[i] is num of subarray left of A[i] with A[i] being the min
        for i in range(n):
            count = 1
            while sl and sl[-1][0] > A[i]:
                count += sl.pop()[1]
            left[i] = count
            sl.append([A[i], count])
        # right[i] is the num subarray right of A[i] with A[i] being the min
        for j in range(n)[::-1]:
            count = 1
            while sr and sr[-1][0] >= A[j]:
                count += sr.pop()[1]
            right[j] = count
            sr.append([A[j], count])
        # print(left,right)
        return sum(a * l * r for a, l, r in zip(A, left, right)) % 1_000_000_007
        


class Solution(object):
    def sumSubarrayMins(self, A):
        MOD = 10**9 + 7

        stack = []
        ans = dot = 0
        for j, y in enumerate(A):
            # Add all answers for subarrays [i, j], i <= j
            count = 1
            while stack and stack[-1][0] >= y:
                x, c = stack.pop()
                count += c
                dot -= x * c

            stack.append((y, count))
            dot += y * count
            ans += dot
        return ans % MOD

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        tot = 0
        stack = [-1]
        A.append(0)
        for i in range(len(A)):
            #print(tot, A[i],'<<<<')
            while A[i] < A[stack[-1]]:
                loc = stack.pop()
                height = A[loc]
                left = loc - stack[-1]
                right = i - loc
                width = i - stack[-1] - 1
                #print(height, left*right)#*(width+1)//2)
                tot += height*left*right#*(width+1)//2
            stack.append(i)
        return tot % (10 ** 9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # Prev/Next Array
        # Time  complexity: O(N)
        # Space complexity: O(N)
        # MOD = 10**9 + 7
        # N = len(A)

        # # prev has i* - 1 in increasing order of A[i* - 1]
        # # where i* is the answer to query j
        # stack, prev = [], [None] * N
        # for i in range(N):
        #     while stack and A[i] <= A[stack[-1]]:
        #         stack.pop()
        #     prev[i] = stack[-1] if stack else -1
        #     stack.append(i)

        # # next has k* + 1 in increasing order of A[k* + 1]
        # # where k* is the answer to query j
        # stack = []
        # next_ = [None] * N
        # for k in range(N - 1, -1, -1):
        #     while stack and A[k] < A[stack[-1]]:
        #         stack.pop()
        #     next_[k] = stack[-1] if stack else N
        #     stack.append(k)

        # # Use prev/next array to count answer
        # return sum((i - prev[i]) * (next_[i] - i) * A[i] for i in range(N)) % MOD


        # Maintain Stack of Minimums
        # Time  complexity: O(N)
        # Space complexity: O(N)
        MOD = 10**9 + 7

        stack, ans, dot = [], 0, 0
        for j, y in enumerate(A):
            # Add all answers for subarrays [i, j], i <= j
            count = 1
            while stack and stack[-1][0] >= y:
                x, c = stack.pop()
                count += c
                dot -= x * c

            stack.append((y, count))
            dot += y * count
            ans += dot

        return ans % MOD



class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left_less = [0] * n
        right_less = [0] * n
        left_stack = []
        right_stack = []
        for i in range(n):
            count = 1
            while left_stack and left_stack[-1][0] > A[i]:
                count += left_stack.pop()[1] 
                # count += 1
            left_less[i] = count
            left_stack.append([A[i], count])
        for i in range(n-1, -1, -1):
            count = 1
            while right_stack and right_stack[-1][0] >= A[i]:
                count += right_stack.pop()[1]
                # count += 1
            right_less[i] = count
            right_stack.append([A[i], count])
            
        mod = 10**9 + 7
        return sum(A[i]*right_less[i]*left_less[i] for i in range(n)) % mod

class Solution(object):
    def sumSubarrayMins(self, A):
        MOD = 10**9 + 7
        N = len(A)

        # prev has i* - 1 in increasing order of A[i* - 1]
        # where i* is the answer to query j
        stack = []
        prev = [None] * N
        for i in range(N):
            count = 1
            while stack and A[i] <= A[stack[-1][0]]:
                x,c = stack.pop()
                count += c
            stack.append((i, count))
            prev[i] = stack[-1][1] if stack else -1
            
        print(prev)
        # next has k* + 1 in increasing order of A[k* + 1]
        # where k* is the answer to query j
        stack = []
        nxt = [None] * N
        for k in range(N-1, -1, -1):
            count = 1
            while stack and A[k] < A[stack[-1][0]]:
                x, c = stack.pop()
                count += c
            stack.append((k, count))    
            nxt[k] = stack[-1][1] if stack else N
            

        # Use prev/next array to count answer
        print(nxt)
        return sum((prev[i]) * (nxt[i]) * A[i]
                   for i in range(N)) % MOD

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n, mod = len(A), 10**9 + 7
        left, right, stack1, stack2 = [0]*n, [0]*n, [], []
        
        for i in range(n):
            count = 1
            while stack1 and stack1[-1][0] > A[i]:
                count += stack1.pop()[1]
            left[i] = count
            stack1.append([A[i], count])
        
        for i in range(n-1, -1, -1):
            count = 1
            while stack2 and stack2[-1][0] >= A[i]:
                count += stack2.pop()[1]
            right[i] = count
            stack2.append([A[i], count])
        
        return sum(a * l * r for a, l, r in zip(A, left, right)) % mod

class Solution(object):
    def sumSubarrayMins(self, A):
        MOD = 10**9 + 7
        n = len(A)

        stack = []
        left = [-1] * n
        for i in range(n):
            while stack and A[i] <= A[stack[-1]]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            stack.append(i)

        stack = []
        right = [n] * n
        for k in range(n-1, -1, -1):
            while stack and A[k] < A[stack[-1]]:
                stack.pop()
            if stack:
                right[k] = stack[-1]
            stack.append(k)

        return sum((i - left[i]) * (right[i] - i) * A[i] for i in range(n)) % MOD

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        
        res=[0]*(len(A)+1)
        A=[0]+A
        stack=[(0,0)]
        
        for i,num in enumerate(A):
            while stack and stack[-1][0]>num:
                stack.pop()
            j=stack[-1][1]
            res[i]=res[j]+(i-j)*num
            stack.append((num,i))
        return sum(res) % (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)

class Solution:
    def sumSubarrayMins(self, A):
        n, mod = len(A), 10**9 + 7
        left, right, s1, s2 = [0] * n, [0] * n, [], []
        for i in range(n):
            count = 1
            while s1 and s1[-1][0] > A[i]: count += s1.pop()[1]
            left[i] = count
            s1.append([A[i], count])
        for i in range(n)[::-1]:
            count = 1
            while s2 and s2[-1][0] >= A[i]: count += s2.pop()[1]
            right[i] = count
            s2.append([A[i], count])
        return sum(a * l * r for a, l, r in zip(A, left, right)) % mod
    
        


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        m = 10 ** 9 + 7
        prev_stack = []
        next_stack = []
        
        prev_smaller = {}
        next_smaller = {}
                
        for i in range(len(A)):
            while len(next_stack) > 0 and next_stack[-1][0] >= A[i]:
                elem, idx = next_stack.pop()
                next_smaller[idx] = i
                
            next_stack.append([A[i], i])
            
        while len(next_stack) != 0:
            elem, idx = next_stack.pop()
            next_smaller[idx] = len(A)
    
        
        for i in range(len(A) - 1, -1, -1):
            while len(prev_stack) > 0 and prev_stack[-1][0] > A[i]:
                elem, idx = prev_stack.pop()
                prev_smaller[idx] = i
                
            prev_stack.append([A[i], i])
            
        while len(prev_stack) != 0:
            elem, idx = prev_stack.pop()
            prev_smaller[idx] = -1
        
        # print(prev_smaller)
        # print(next_smaller)
        
        result = 0
        for i in range(len(A)):
            left_count = i - prev_smaller[i] - 1
            right_count = next_smaller[i] - i - 1
            num_occurrences = (left_count + 1) * (right_count + 1)
            result = (result + num_occurrences * A[i]) % m
            
        return result


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod = 10**9+7
        A = [0] + A + [0]
        n = len(A)
        stack = []
        res = 0
        
        for i in range(n):
            while stack and A[stack[-1]]>A[i]:
                curr = stack.pop(-1)
                left = stack[-1]
                right = i
                res += A[curr]*(curr-left)*(right-curr)   
            stack.append(i)
        res %= 10 ** 9 + 7
        return res


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        stack = []
        l_count = []
        for i in range(n):
            while stack and A[stack[-1]]>A[i]:
                stack.pop()
            l_c = 0
            if stack:
                l_c = stack[-1] + 1
            stack.append(i)
            l_count.append(l_c)
        
        stack = []
        r_count = []
        for i in range(n):
            while stack and A[stack[-1]]>=A[n-i-1]:
                stack.pop()
            r_c = n-1
            if stack:
                r_c = stack[-1] - 1
            stack.append(n-i-1)
            r_count.append(r_c)
        
        r_count = r_count[::-1]
        
        t = 0
        print(l_count)
        print(r_count)
        for i in range(n):
            l = l_count[i]
            r = r_count[i]
            t += (i-l+1)*(r-i+1)*A[i]
        
        return t % (10**9+7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod = 10 ** 9 + 7
        stack = []
        ans = dot = 0
        for idx, val in enumerate(A):
            count = 1
            while stack and stack[-1][0] >= val:
                x,c = stack.pop()
                count += c
                dot -= x*c
            
            stack.append((val,count))
            dot += val * count
            ans += dot
        return ans % mod

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        N = len(A)
        stack = []
        res = 0
        instack = 0
        for i in range(N):
            tmp = 1
            while stack and stack[-1][0]>=A[i]:
                x, cnt = stack.pop()
                tmp += cnt
                instack -= x*cnt
            stack.append( (A[i], tmp) )
            instack += A[i]*tmp
            
            res += instack
        return res % (10**9+7)

from collections import deque
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        stack = deque()
        left = [0] * len(A)
        right = [len(A)] * len(A)
        mod = 10**9 + 7
        
        for i in range(len(A)):
            #print(stack, left, right)
            while stack and A[stack[-1]] > A[i]:
                right[stack[-1]] = i
                stack.pop()
            left[i] = stack[-1] if stack else -1
            stack.append(i)
        
        res = 0
        for i in range(len(A)):
            res += A[i] * (i-left[i]) * (right[i]-i)
        return res%mod

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        length = len(A)
        left = [-1 for _ in range(length)]
        right = [length for _ in range(length)]
        stack, res, N = [], 0, 10 ** 9 + 7
        
        for i in range(length):
            while stack and A[stack[-1]] > A[i]:
                right[stack.pop()] = i
            if stack: left[i] = stack[-1]
            stack.append(i)
        
        # print(left)
        # print(right)
        
        for i in range(length):
            res += (i - left[i]) * (right[i] - i) * A[i]
        return res % N


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        length = len(A)
        left = [-1 for _ in range(length)]
        right = [length for _ in range(length)]
        stack, res, N = [], 0, 10 ** 9 + 7
        
        for i in range(length):
            while stack and A[stack[-1]] > A[i]:
                right[stack.pop()] = i
            if stack: left[i] = stack[-1]
            stack.append(i)
        
        for i in range(length):
            res += (i - left[i]) * (right[i] - i) * A[i]
        return res % N


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod = 10 ** 9 + 7
        left, right = self.findFirstSmaller(A)
        ans = 0
        for i in range(len(A)):
            ans += ((A[i] % mod)  * ((right[i] - 1 - i + 1) * (i - (left[i] + 1) + 1))) % mod
    
        return ans % mod
        
    
    
    def findFirstSmaller(self, A):
        left, right = [-1] * len(A), [len(A)] * len(A)
        
        stack = []
        
        for i, n in enumerate(A):
            while stack and stack[-1][0] > n:
                right[stack.pop()[1]] = i
            
            if stack:
                left[i] = stack[-1][1]
            
            stack.append((n, i))
            
        return left, right

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res = 0
        s = []
        A = [0] + A + [0]
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10**9 + 7)


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        stack=[-1]
        A.append(float('-inf'))
        res=0
        for i, num in enumerate(A):
            while A[stack[-1]] > num:
                center= stack.pop()
                res+= (i-center)* (center-stack[-1])*A[center]
            stack.append(i)
        return res% (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n, mod = len(A), 10**9+7
        s = []
        left = [i + 1 for i in range(n)]
        right = [n - i for i in range(n)]
        
        res = 0
        
        for i in range(n):
            while s and A[s[-1]] > A[i]:
                k = s.pop()
                right[k] = i - k
            left[i] = i + 1 if not s else i - s[-1]
            s.append(i)
        print(right)
        print(left)
        
        return sum(a*i*j for a,i,j in zip(A,left,right)) % mod

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        left = []
        right = []
        stack = []
        
        for i in range(len(A)):
            left.append(i + 1)
            right.append(len(A) - i)
        
        for i in range(len(A)):
            while stack and A[i] < A[stack[-1]]:
                poppedIdx = stack.pop()
                right[poppedIdx] = i - poppedIdx
            
            if stack:
                left[i] = i - stack[-1]
            else:
                left[i] = i + 1
            
            stack.append(i)
        
        ans = 0
        for i in range(len(A)):
            ans = (ans + left[i] * right[i] * A[i]) % 1000000007
            
        return ans

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        
        N = len(A)
        stack = []
        left, right = [None]*N,  [None]*N
        
        for i in range(N):
            # print(stack)
            while stack and A[i] <= A[stack[-1]]:
                stack.pop()
                
            left[i] = stack[-1] if stack else -1
            stack.append(i)
        # print(left)
        stack.clear()
        
        for i in range(N-1, -1, -1):
            while stack and A[i] < A[stack[-1]]:
                stack.pop()
            right[i] = stack[-1] if stack else N
            stack.append(i)
        # print(right)
        
        count = 0
        
        for i in range(N):
            count += (i-left[i])* (right[i]-i)*A[i]
        return count % (10**9 + 7)
        
        
        
        
        


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        MOD = 10 ** 9 + 7           
        n = len(A)
        
        # previous less element
        stack = []
        left = [None] * n
        for i in range(n):
            while stack and A[i] <= A[stack[-1]]:
                stack.pop()
            if stack:
                left[i] = stack[-1]
            else:
                left[i] = -1
            stack.append(i)
        # next less element
        # stack = []
        # right = [None] * n
        # for i in range(n-1,-1,-1):
        #     # note A[i] < A[stack[-1]]
        #     while stack and A[i] < A[stack[-1]]:
        #         stack.pop()
        #     # note right[i] = n if not stack
        #     right[i] = stack[-1] if stack else n
        #     stack.append(i)
        stack = []
        right = [n] * n
        for i in range(n):
            while stack and A[i] <= A[stack[-1]]:
                right[stack.pop()] = i
            stack.append(i)
        
        res = 0
        for i in range(n):
            res += (i-left[i]) * (right[i]-i) * A[i]
        
        return res % MOD

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        N = len(A)
        if N == 0: return 0
        mod = 10**9 + 7                
        
        stack, left, right = [], [0] * N, [0] * N
        
        for i in range(N):
            count = 1
            while stack and stack[-1][0] > A[i]: count += stack.pop()[1]
            left[i] = count
            stack.append((A[i], count))
            
        stack.clear() 
        
        for i in range(N - 1, -1, -1):
            count = 1
            while stack and stack[-1][0] >= A[i]: count += stack.pop()[1]
            right[i] = count            
            stack.append((A[i], count))
            
        return sum([l*r*v for l,r,v in zip(left, right, A)]) % mod

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        N = len(A)
        if N == 0: return 0
        mod = 10**9 + 7                
        
        stack, left, right = [], [0] * N, [0] * N
        
        for i in range(N):
            while stack and A[stack[-1]] > A[i]: stack.pop()
            left[i] = i - (stack[-1] if stack else -1)       
            stack.append(i)
            
        stack.clear() 
        
        for i in range(N - 1, -1, -1):
            while stack and A[stack[-1]] >= A[i]: stack.pop()
            right[i] = stack[-1] - i if stack else N - i        
            stack.append(i)
            
        return sum([l*r*v for l,r,v in zip(left, right, A)]) % mod


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # https://buptwc.com/2018/09/16/Leetcode-907-Sum-of-Subarray-Minimums/
        mod = 10 ** 9 + 7
        left = [-1] * len(A)
        right = [len(A)] * len(A)
        
        # 计算left数组
        stack = [0]
        for i in range(1,len(A)):
            if A[i] > A[stack[-1]]:
                left[i] = stack[-1]
            else:
                while stack and A[i] <= A[stack[-1]]: 
                    stack.pop()
                if not stack: 
                    left[i] = -1
                else: 
                    left[i] = stack[-1]
            stack.append(i)
            
        # 计算right数组
        stack = [len(A)-1]
        for i in range(len(A)-2,-1,-1):
            if A[i] > A[stack[-1]]:
                right[i] = stack[-1]
            else:
                while stack and A[i] < A[stack[-1]]: 
                    stack.pop()
                if not stack: 
                    right[i] = len(A)
                else: 
                    right[i] = stack[-1]
            stack.append(i)

        res = 0
        for i in range(len(A)):
            res += A[i] * (i - left[i]) * (right[i]-  i)
            
        return res % mod

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res = 0
        #stack store the index of non-decreasing numbers
        stack = []
        A = [float('-inf')] + A + [float('-inf')]
        
        for i, n in enumerate(A):
            #if n is smaller than the last element in stack
            #pop until it is the largest
            while stack and A[stack[-1]] > n:
                cur = stack.pop()
                #after pop, the stack[-1] has the index of the first element that is smaller than cur. i is the right boundary 
                res += A[cur] * (cur - stack[-1]) * (i - cur)
            stack.append(i)
        
        return res % (10**9+7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        N = len(A)
        if N == 0: return 0
        mod = 10**9 + 7                
        
        stackLeft, stackRight, left, right = [], [], [0] * N, [0] * N
        
        for L in range(N):
            while stackLeft and A[stackLeft[-1]] > A[L]: stackLeft.pop()
            left[L] = L - (stackLeft[-1] if stackLeft else -1)       
            stackLeft.append(L)
            R = N - L - 1
            while stackRight and A[stackRight[-1]] >= A[R]: stackRight.pop()
            right[R] = stackRight[-1] - R if stackRight else N - R        
            stackRight.append(R)
            
        return sum([l*r*v for l,r,v in zip(left, right, A)]) % mod


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left, right = [i + 1 for i in range(n)], [n - i for i in range(n)]
        stackp, stackn = [], []
        for i, num in enumerate(A):
            while stackp and num < A[stackp[-1]]: stackp.pop()
            if stackp: left[i] = i - stackp[-1]
            stackp.append(i)
            
            while stackn and num < A[stackn[-1]]:
                curr = stackn.pop()
                right[curr] = i - curr
            stackn.append(i)


        res = 0
        mod = 10**9 + 7
        for i, num in enumerate(A):
            res = (res + left[i]*right[i]*num) % mod
        return res

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        MOD = pow(10,9)+7
        N = len(A)
        prev = [None]*N
        next_ = [None]*N
        
        stack=[]
        for i in range(N):
            while stack and A[i]<=A[stack[-1]]:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)
        
        stack=[]
        for k in range(N-1,-1,-1):
            while stack and A[k]<A[stack[-1]]:
                stack.pop()
            next_[k] = stack[-1] if stack else N
            stack.append(k)
        
        # print(prev)
        # print(next_)
        
        return sum((i-prev[i])*(next_[i]-i)*A[i] for i in range(N))%MOD


class Solution:
    # def sumSubarrayMins(self, A: List[int]) -> int:
    #     mins = []
    #     for i, x in enumerate(A):
    #         mins.append(x)
    #         current_min = x
    #         for j in range(i+1, len(A)):
    #             if A[j] < current_min:
    #                 current_min = A[j]
    #             mins.append(current_min)
    #     # print(mins)
    #     return int((sum(mins) % (10**9 + 7)))
    def sumSubarrayMins(self, A: List[int]) -> int:
        ple_stack = []
        left = [-1] * len(A)
        for i in range(len(A)):
            # print(ple_stack)
            while ple_stack and A[i] < A[ple_stack[-1]]:
                ple_stack.pop()
            left[i] = ple_stack[-1] if ple_stack else -1
            # print(left)
            ple_stack.append(i)
        for i in range(len(A)):
            left[i] =  i - left[i]
        # print(left)
        
        
        nle_stack = []
        right = [-1] * len(A)
        for j in reversed(range(len(A))):
            # print(nle_stack)
            while nle_stack and A[j] <= A[nle_stack[-1]]:
                nle_stack.pop()
            right[j] = nle_stack[-1] if nle_stack else len(A)
            # print(right)
            nle_stack.append(j)
        for j in range(len(A)):
            right[j] = right[j] - j
        # print(right)
        
        return sum([x * y * z for x, y, z in zip(left, right, A)]) % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        N = len(A)
        if N == 0: return 0
        mod = 10**9 + 7                
        
        stack, left, right = [], [0] * N, [0] * N
        
        for i in range(N):
            count = 1
            while stack and stack[-1][0] > A[i]: count += stack.pop()[1]
            left[i] = count
            stack.append((A[i], count))
            
        stack.clear() 
        
        for i in range(N - 1, -1, -1):
            count = 1
            while stack and stack[-1][0] >= A[i]: count += stack.pop()[1]
            right[i] = count            
            stack.append((A[i], count))
            
        total = 0
            
        for l,r,v in zip(left, right, A):
            total += l*r*v
                
        
        return total % mod
    
    
        # # [2,3,1,2,4,6]
        # # 21 subarrays
        #      2 1 1 1 1


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left, right = [i + 1 for i in range(n)], [n - i for i in range(n)]
        stackp, stackn = [], []
        for i, num in enumerate(A):
            while stackp and num < A[stackp[-1]]: stackp.pop()
            left[i] = i - stackp[-1] if stackp else i + 1
            stackp.append(i)
            
            while stackn and num < A[stackn[-1]]:
                curr = stackn.pop()
                right[curr] = i - curr
            stackn.append(i)


        res = 0
        mod = 10**9 + 7
        for i, num in enumerate(A):
            res = (res + left[i]*right[i]*num) % mod
        return res

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod=10**9+7
        left,right=self.PLE(A),self.NLE(A)
        return sum(a*i*j for (a,i,j) in zip(A,left,right)) % mod
    
    def PLE(self,A):
        n=len(A)
        left=[-1]*n
        stack=[]
        for i in range(n):
            while stack and A[stack[-1]]>A[i]:
                stack.pop()
            if stack:
                left[i]=stack[-1]
            stack.append(i)
        
        for i in range(n):
            left[i]=i+1 if left[i]==-1 else i-left[i]
        return left
    
    def NLE(self,A):
        n=len(A)
        right=[-1]*n
        stack=[]
        for i in range(n):
            while stack and A[stack[-1]]>A[i]:
                right[stack.pop()]=i
            stack.append(i)
        
        for i in range(n):
            right[i]=n-i if right[i]==-1 else right[i]-i
        return right


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n, mod = len(A), 10**9 + 7
        left, right, s1, s2 = [0] * n, [0] * n, [], []
        for i in range(n):
            count = 1
            while s1 and s1[-1][0] > A[i]: count += s1.pop()[1]
            left[i] = count
            s1.append([A[i], count])
        for i in range(n)[::-1]:
            count = 1
            while s2 and s2[-1][0] >= A[i]: count += s2.pop()[1]
            right[i] = count
            s2.append([A[i], count])
        return sum(a * l * r for a, l, r in zip(A, left, right)) % mod


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        
        MOD = 10**9 + 7
        cl = []
        stack = []
        for i in range(len(A)):
            
            while stack and A[stack[-1]] > A[i]:
                stack.pop()
            
            if not stack:
                l = i+1
            else:
                l = i - stack[-1]
            cl.append(l)
            stack.append(i)
        
        
        cr = []
        stack = []
        for i in range(len(A)-1, -1, -1):
            while stack and A[stack[-1]] >= A[i]:
                stack.pop()
            
            if not stack:
                r = len(A) - i
            else:
                r = stack[-1] - i
            
            stack.append(i)
            cr.append(r)
        
        cr = cr[::-1]
        
        tot = 0
        for i in range(len(A)):
            tot += A[i]*cl[i]*cr[i]
            tot %= 10**9 + 7
        
        return tot
        '''
        queue = deque()
        MOD = 10**9 + 7
        
        tot = 0
        for indx, num in enumerate(A):
            tot += num
            queue.append((num,indx+1))
            
        while queue:
            sub_min, indx = queue.popleft()
            if indx < len(A):
                new_sub_min = min(sub_min, A[indx])
                queue.append((new_sub_min, indx+1))
                tot += new_sub_min
                tot %= MOD
        
        return tot
        '''

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res = 0
        s = []
        A = [0] + A + [0]
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10**9 + 7)


from queue import deque
from collections import defaultdict
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        A=[float('-inf')]+A+[float('-inf')]
        
        left=deque()
        left.append(0)
        right=deque()
        right.appendleft(len(A)-1)
        
        left_b=defaultdict(int)
        right_b=defaultdict(int)
        
        for i in range(1,len(A)-1):
            while left and A[left[-1]]>A[i]:
                left.pop()
            left_b[i]=left[-1]+1
            left.append(i)
        
        for i in reversed(range(1,len(A)-1)):
            while right and A[right[0]]>=A[i]:
                right.popleft()
            right_b[i]=right[0]-1
            right.appendleft(i)
        
        
        
        res=0
        for i in range(1,len(A)-1):
            res+=(i-left_b[i]+1)*(right_b[i]-i+1)*A[i]
        return res%(10**9+7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l = len(A)
        left = [0 for _ in range(l)]
        right = [0 for _ in range(l)]
        s = []
        res = 0
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] < A[s[-1]]:
                        s.pop()
                    if s == []:
                        left[i] = i
                    else:
                        left[i] = i - s[-1] - 1
                    s.append(i)
            else:
                s.append(i)
        A = A[::-1]
        s = []
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] <= A[s[-1]]:
                        s.pop()
                    if s == []:
                        right[i] = i
                    else:
                        right[i] = i - s[-1] -1
                    s.append(i)
            else:
                s.append(i)
        for i in range(l):
            res += A[l-1-i] * (left[i]+1) * (right[l-1-i]+1)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l = len(A)
        left = [0 for _ in range(l)]
        right = [0 for _ in range(l)]
        s = []
        res = 0
        for i in range(l):
            if s:
                if A[i] < A[s[-1]]:
                    while s and A[i] < A[s[-1]]:
                        s.pop()
                    if s == []:
                        left[i] = i
                    else:
                        left[i] = i - s[-1] - 1
            s.append(i)
        A.reverse()
        s.clear()
        for i in range(l):
            if s:
                if A[i] <= A[s[-1]]:
                    while s and A[i] <= A[s[-1]]:
                        s.pop()
                    if s == []:
                        right[i] = i
                    else:
                        right[i] = i - s[-1] -1
            s.append(i)
        for i in range(l):
            if left[i] == 0 and right[l-1-i] == 0:
                res += A[l-1-i]
            else:
                res += A[l-1-i] * (left[i]+1) * (right[l-1-i]+1)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # 자존감이 낮아지면 힘들다...
        # 내가 노력한 양에 비해 남들의 평가가 낮게 돌아오는것 같기에
        # 이것또한 내가 생각하는 기준! 
        
        # when i see this is minimum on num on left side
        # i can count the number 
        # cnt = 1
        # while st and st[-1][0] > curr_num:
        #     pop and increment
        # what happend for increase case? then this case count only once when it used by itself
        N = len(A)
        lefts = []
        st = []
        for i,num in enumerate(A):
            cnt = 1
            while st and st[-1][0] > num:
                prev_num, prev_cnt = st.pop()
                cnt += prev_cnt
            st.append([num, cnt])
            lefts.append(cnt)
        rights = []
        st = []
        for i,num in reversed(list(enumerate(A))):
            cnt = 1
            while st and st[-1][0] >= num:
                prev_num, prev_cnt = st.pop()
                cnt += prev_cnt
            st.append([num, cnt])
            rights.append(cnt)

        
        ans = 0
        for lc, num, rc in zip(lefts, A, rights[::-1]):
            ans += lc*num*rc
        return ans % (10**9+7)


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        s=[]
        n = len(A)
        left =[1]*n
        right = [1]*n
        for i in range(n):
            while len(s)>0 and s[-1][0]>=A[i]:
                val, cnt = s.pop()
                left[i] += cnt
            s.append([A[i], left[i]])
            
        s = []
        for i in range(n-1, -1, -1):
            while len(s)>0 and s[-1][0]>A[i]:
                val, cnt = s.pop()
                right[i] += cnt
            s.append((A[i], right[i]))
            
        total = 0
        for a, l, r in zip(A, left, right):
            total += a*l*r
        return total%(10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod = 10**9+7
        curr_sum = 0
        last_sum = 0
        stack = []

        for a in A:
            cnt = 1
            last_sum = (last_sum + a)%mod
            while stack and a < stack[-1][0]:
                b, c = stack.pop()
                cnt = (cnt + c)%mod
                last_sum = (last_sum - (b-a)*c)%mod

            if stack and stack[-1][0] == a:
                stack[-1][1] = (stack[-1][1] + cnt)%mod
            else:
                stack.append([a, cnt])

            curr_sum = (curr_sum + last_sum)%mod

        return curr_sum

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        result = 0
        tempDq = []
        A = [0] + A + [0]
        for idx in range(len(A)):
            while tempDq and A[tempDq[-1]] > A[idx]:
                prevIdx = tempDq.pop()
                lastIdx = tempDq[-1]
                result += A[prevIdx] * (prevIdx - lastIdx) * (idx - prevIdx)
            tempDq.append(idx)
        return result % (10 ** 9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        s=[]
        n = len(A)
        left =[1]*n
        right = [1]*n
        for i in range(n):
            while len(s)>0 and s[-1][0]>A[i]:
                val, cnt = s.pop()
                left[i] += cnt
            s.append([A[i], left[i]])
            
        s = []
        for i in range(n-1, -1, -1):
            while len(s)>0 and s[-1][0]>=A[i]:
                val, cnt = s.pop()
                right[i] += cnt
            s.append((A[i], right[i]))
            
        total = 0
        for a, l, r in zip(A, left, right):
            total += a*l*r
        return total%(10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        A = [0] + A
        stack = [0]
        result = [0] * len(A)
        
        for i in range(len(A)):
            while A[stack[-1]] > A[i]:
                stack.pop()
                
            j = stack[-1]
            result[i] = result[j] + (i - j) * A[i]
            stack.append(i)
        return sum(result) % (10 ** 9 + 7)


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        s = []
        left = [None]*len(A)
        for i in range(len(A)):
            count=1
            while len(s)>0 and A[i]<=s[-1][0]:
                count += s.pop()[1]
            s.append((A[i],count))
            left[i] = count
        s = []
        right = [None]*len(A)
        for i in range(len(A)-1,-1,-1):
            count=1
            while len(s)>0 and A[i]<s[-1][0]:
                count+=s.pop()[1]
            s.append((A[i],count))
            right[i] = count
        _sum = 0
        for i in range(len(A)):
            _sum=_sum+A[i]*(left[i]*right[i])
        return int(_sum%(1e9 + 7))
        
            


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l = len(A)
        left = [0] * l
        right = [0] * l
        s = []
        res = 0
        for i in range(l):
            if s and A[i] < A[s[-1]]:
                while s and A[i] < A[s[-1]]:
                    s.pop()
                if s == []:
                    left[i] = i
                else:
                    left[i] = i - s[-1] - 1
            s.append(i)
        A.reverse()
        s.clear()
        for i in range(l):
            if s and A[i] <= A[s[-1]]:
                while s and A[i] <= A[s[-1]]:
                    s.pop()
                if s == []:
                    right[i] = i
                else:
                    right[i] = i - s[-1] - 1
            s.append(i)
        for i in range(l):
            res += A[l-1-i] * (left[i]+1) * (right[l-1-i]+1)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l = len(A)
        left = [0 for _ in range(l)]
        right = [0 for _ in range(l)]
        s = []
        res = 0
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] < A[s[-1]]:
                        s.pop()
                    if s == []:
                        left[i] = i
                    else:
                        left[i] = i - s[-1] - 1
                    s.append(i)
            else:
                s.append(i)
        A = A[::-1]
        s = []
        for i in range(l):
            if s:
                if A[i] <= A[s[-1]]:
                    while s and A[i] <= A[s[-1]]:
                        s.pop()
                    if s == []:
                        right[i] = i
                    else:
                        right[i] = i - s[-1] -1
            s.append(i)
        for i in range(l):
            res += A[l-1-i] * (left[i]+1) * (right[l-1-i]+1)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        ans=0
        
        
        st=[]
        n=len(A)
        left=[0]*n
        right=[0]*n
        mod=pow(10,9)+7
        for i in range(len(A)):
            c=1
            while st and st[-1][0]>A[i]:
                c+=st.pop()[1]
            
            left[i]=c
            st.append((A[i],c))
        
        
        st=[]
        for i in list(range(len(A)))[::-1]:
            c=1
            while st and st[-1][0]>=A[i]:
                c+=st.pop()[1]
            
            right[i]=c
            
            st.append((A[i],c))
        
        ans=0
        m=pow(10,9)+7
        
        print(left)
        print(right)
        for a,b,c in zip(A,left,right):
            ans+=a*b*c 
            ans=ans%m
                      
        return ans

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        s1,s2 = [],[]
        left = [None]*len(A)
        right = [None]*len(A)
        
        for i in range(len(A)):
            count=1
            while len(s1)>0 and A[i]<=s1[-1][0]:
                count += s1.pop()[1]
            s1.append((A[i],count))
            left[i] = count
        
        for i in range(len(A)-1,-1,-1):
            count=1
            while len(s2)>0 and A[i]<s2[-1][0]:
                count+=s2.pop()[1]
            s2.append((A[i],count))
            right[i] = count
        _sum = 0
        for i in range(len(A)):
            _sum=_sum+A[i]*(left[i]*right[i])
        return int(_sum%(1e9 + 7))
        
            


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        N = len(A)
        if N == 0: return 0
        mod = 10**9 + 7                
        
        res = 0
        s = []
        A = [0] + A + [0]
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % mod


class Solution:

    def next_smallest(self, A):
        
        inds = [-1]*len(A)

        stack = []

        for i, val in enumerate(A):

            while len(stack)>0 and A[stack[-1]]>val:
                inds[stack[-1]] = i
                stack.pop()

            stack+=[i]
            
        return inds

    def last_smallest(self, A):

        inds = [-1]*len(A)

        stack = []

        for i, val in reversed(list(enumerate(A))):

            while len(stack)>0 and A[stack[-1]]>=val:
                inds[stack[-1]] = i
                stack.pop()

            stack+=[i]
            
        return inds
        

    def sumSubarrayMins(self, A):

        left = self.last_smallest(A)
        right = self.next_smallest(A)

        tot = 0

        n = len(A)

        for i, val in enumerate(A):
            
            p = left[i]
            q = right[i]

            a = i-p
            b = q-i

            if p==-1:
                a = i+1

            if q==-1:
                b = n-i

            nseqs = a*b

            tot+=nseqs*val

        return tot % (10**9+7)


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        ans = 0
        A = [float('-inf')] + A + [float('-inf')]
        stack = []
        for i, a in enumerate(A):
            while stack and A[stack[-1]] > a:
                cur = stack.pop()
                ans += A[cur] * (i-cur) * (cur-stack[-1])
            stack.append(i)
        return ans % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l = len(A)
        left = [0 for _ in range(l)]
        right = [0 for _ in range(l)]
        s = []
        res = 0
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] < A[s[-1]]:
                        pre = s.pop()
                    if s == []:
                        left[i] = i
                    else:
                        left[i] = i - s[-1] - 1
                    s.append(i)
            else:
                s.append(i)
            #print(s)
        #print(left)
        A = A[::-1]
        s = []
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] <= A[s[-1]]:
                        pre = s.pop()
                    if s == []:
                        right[i] = i
                    else:
                        right[i] = i - s[-1] -1
                    s.append(i)
            else:
                s.append(i)
        right = right[::-1]
        #print(right)
        A = A[::-1]
        for i in range(l):
            res += A[i] * (left[i]+1) * (right[i]+1)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        s1,s2 = [],[]
        left = [None]*len(A)
        right = [None]*len(A)
        
        for i in range(len(A)):
            count1=1
            while len(s1)>0 and A[i]<=s1[-1][0]:
                count1=count1+s1.pop()[1]
            s1.append((A[i],count1))
            left[i] = count1
            #for j in range(len(A)-1,-1,-1):
            j = len(A)-1-i
            count2=1
            while len(s2)>0 and A[j]<s2[-1][0]:
                count2+=s2.pop()[1]
            s2.append((A[j],count2))
            right[j] = count2
        _sum = 0
        for i in range(len(A)):
            _sum=_sum+A[i]*(left[i]*right[i])
        return int(_sum%(1e9 + 7))
        
            


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l, r = [None]*len(A), [None]*len(A)
        s1, s2 =[], []
        for i in range(len(A)):
            c = 1
            while s1 and (s1[-1][0]>= A[i]):
                c += s1[-1][1]
                s1.pop(-1)
                
            s1.append([A[i], c])
            l[i] = c
            
        for i in range(len(A)-1, -1, -1):
            c = 1
            while s2 and(s2[-1][0] > A[i]):
                c += s2[-1][1]
                s2.pop(-1)
            s2.append([A[i], c])
            r[i] = c
        result = 0
        
        for i in range(len(A)):
            result += A[i]*l[i]*r[i]
        return result%(10**9 + 7)
    


MOD = 1000000007
class Solution:
    def sumSubarrayMins(self, A):
        A = [0] + A + [0]
        stack = []
        res = 0
        for right in range(len(A)):
            while stack and A[stack[-1]] > A[right]:
                mid = stack.pop()
                left = stack[-1]
                res += A[mid] * (mid - left) * (right - mid)
                res %= MOD
            stack.append(right)
        return res

class Solution:
    def previousLessNumber(self, A: List[int]) -> List[int]:
        plmStack = []
        plmResult = [-1] * len(A)
        i = 0
        while (i < len(A)):
            while(len(plmStack) > 0 and A[plmStack[-1]] >= A[i]):
                plmStack.pop()
            plmResult[i] = -1 if len(plmStack) == 0 else plmStack[-1]
            plmStack.append(i)
            i += 1
        return plmResult
    
    def nextLessNumber(self, A: List[int]) -> List[int]:
        nlmStack = []
        nlmResult = [-1] * len(A)
        i = len(A)-1
        while (i >= 0):
            while(len(nlmStack) > 0 and A[nlmStack[-1]] > A[i]):
                nlmStack.pop()
            nlmResult[i] = -1 if len(nlmStack) == 0 else nlmStack[-1]
            nlmStack.append(i)
            i -= 1
        return nlmResult
        
    def sumSubarrayMins(self, A: List[int]) -> int:
        plmResult = self.previousLessNumber(A)
        nlmResult = self.nextLessNumber(A)
        print(plmResult)
        print(nlmResult)
        sum = 0
        for i in range(len(A)):
            leftDist = 0 
            if plmResult[i] == -1:
                leftDist = i + 1
            else:
                leftDist = i - plmResult[i]
                
            rightDist = 0 
            if nlmResult[i] == -1:
                rightDist = len(A) - i
            else:
                rightDist = nlmResult[i] - i
            
            # print(\"index\", i , \"left\", leftDist, \"right\", rightDist)
            sum = (sum + (A[i] * leftDist * rightDist)) % (10**9 + 7)
        return sum


class Solution:
    def previousLessNumber(self, A: List[int]) -> List[int]:
        plmStack = []
        plmResult = [-1] * len(A)
        i = 0
        while (i < len(A)):
            while(len(plmStack) > 0 and A[plmStack[-1]] > A[i]):
                plmStack.pop()
            plmResult[i] = -1 if len(plmStack) == 0 else plmStack[-1]
            plmStack.append(i)
            i += 1
        return plmResult
    
    def nextLessNumber(self, A: List[int]) -> List[int]:
        nlmStack = []
        nlmResult = [-1] * len(A)
        i = len(A)-1
        while (i >= 0):
            while(len(nlmStack) > 0 and A[nlmStack[-1]] >= A[i]):
                nlmStack.pop()
            nlmResult[i] = -1 if len(nlmStack) == 0 else nlmStack[-1]
            nlmStack.append(i)
            i -= 1
        return nlmResult
        
    def sumSubarrayMins(self, A: List[int]) -> int:
        plmResult = self.previousLessNumber(A)
        nlmResult = self.nextLessNumber(A)
        sum = 0
        for i in range(len(A)):
            leftDist = 0 
            if plmResult[i] == -1:
                leftDist = i + 1
            else:
                leftDist = i - plmResult[i]
                
            rightDist = 0 
            if nlmResult[i] == -1:
                rightDist = len(A) - i
            else:
                rightDist = nlmResult[i] - i
            sum = (sum + (A[i] * leftDist * rightDist)) % (10**9 + 7)
        return sum


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        m = 10 ** 9 + 7
        prev_stack = []
        next_stack = []
        
        prev_smaller = {}
        next_smaller = {}
                
        for i in range(len(A)):
            while len(next_stack) > 0 and A[next_stack[-1]] >= A[i]:
                idx = next_stack.pop()
                next_smaller[idx] = i
                
            next_stack.append(i)
            
        while len(next_stack) != 0:
            idx = next_stack.pop()
            next_smaller[idx] = len(A)
    
        for i in range(len(A) - 1, -1, -1):
            while len(prev_stack) > 0 and A[prev_stack[-1]] > A[i]:
                idx = prev_stack.pop()
                prev_smaller[idx] = i
                
            prev_stack.append(i)
            
        while len(prev_stack) != 0:
            idx = prev_stack.pop()
            prev_smaller[idx] = -1
        
        # print(prev_smaller)
        # print(next_smaller)
        
        result = 0
        for i in range(len(A)):
            left_count = i - prev_smaller[i] - 1
            right_count = next_smaller[i] - i - 1
            num_occurrences = (left_count + 1) * (right_count + 1)
            result = (result + num_occurrences * A[i]) % m
            
        return result


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res = 0
        A = [0] + A + [0]
        stack = []
        for i in range(len(A)):
            while stack and A[stack[-1]] > A[i]:
                j = stack.pop()
                res += A[j] * (i-j) * (j-stack[-1])
            stack.append(i)
        return res % (10**9+7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res = 0
        stack = []
        A = [float('-inf')] + A + [float('-inf')]
        for i, n in enumerate(A):
            while stack and A[stack[-1]] > n:
                cur = stack.pop()
                res += A[cur]*(i-cur)*(cur-stack[-1])
            stack.append(i)
        return res % (10**9 + 7)

        
# class Solution:
#     def sumSubarrayMins(self, A):
#         res = 0
#         stack = []  #  non-decreasing 
#         A = [float('-inf')] + A + [float('-inf')]
#         for i, n in enumerate(A):
#             while stack and A[stack[-1]] > n:
#                 cur = stack.pop()
#                 res += A[cur] * (i - cur) * (cur - stack[-1]) 
#             stack.append(i)
#         return res % (10**9 + 7)


import numpy as np

class Solution:
#     def __init__(self):
#         self.subar = []
#         self.mins = []
#         self.mins_sum = 0
    
#     def getSubarrays(self, A):
#         min_cur = A[0]
#         for i in range(len(A)):
#             if A[i] < min_cur: 
#                 min_cur = A[i]
#                 # print(min_cur)
#             self.mins_sum += min_cur
#             # print(A[:(i+1)], \"min {} sum {}\".format(min_cur, self.mins_sum))
#             # self.mins.append(min_cur)
#             # self.subar.append(A[:i])
        
#         if len(A) > 1:
#             self.getSubarrays(A[1:])
    
    
    
#     def sumSubarrayMins(self, A: List[int]) -> int:
#         if len(A) > 0: self.getSubarrays(A)
#         # print(self.subar)
#         # mins = [np.min(arr) for arr in self.subar]
#         # print(mins)
#         # return int(np.sum(mins) % (10**9 + 7))
#         return int(self.mins_sum % (10**9 + 7))
        
    
     def sumSubarrayMins(self, A: List[int]) -> int:
            stack = []
            left, right = [],[]
            for i in range(len(A)):
                cnt = 1
                while stack and A[i] <= stack[-1][0]:
                    cnt += stack[-1][1]
                    stack.pop()
                stack.append([A[i], cnt])
                left.append(cnt)
            
            stack = []
            for i in range(len(A)-1,-1,-1):
                cnt = 1
                while stack and A[i] < stack[-1][0]:
                    cnt += stack[-1][1]
                    stack.pop()
                stack.append([A[i], cnt])
                right.append(cnt)
            
            right = right[::-1]
            # print(left, right)
            res = 0
            for i in range(len(A)):
                res += A[i] * left[i] * right[i]
            
            return res % (10**9 + 7)
            


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        MOD=10**9+7
        result=0
        stack=[]
        my_dict={}
        
        for i in range(0,len(A)):
            if stack==[]:
                stack.append((i,A[i]))
                my_dict[(i,A[i])]=[0]
            elif A[i]>=stack[-1][1]:
                stack.append((i,A[i]))
                my_dict[(i,A[i])]=[0]
            else:
                while(stack!=[] and A[i]<stack[-1][1]):
                    temp=stack.pop()
                    my_dict[temp].append(i-temp[0]-1)
                if stack==[]:
                    stack.append((i,A[i]))
                    my_dict[(i,A[i])]=[i]
                else:
                    stack.append((i,A[i]))
                    my_dict[(i,A[i])]=[i-1-stack[-2][0]]
        for key in my_dict:
            if len(my_dict[key])==1:
                my_dict[key].append(len(A)-1-key[0])
            result+=key[1]*(my_dict[key][0]+1)*(my_dict[key][1]+1)
        return result%MOD
                


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        stack = []
        bound = [[0, 0] for x in range(0, len(A))]
        for i in range(0, len(A)):
            while 0 < len(stack) and A[i] <= stack[-1][0]: 
                bound[stack[-1][1]][1] = i
                stack.pop()
            stack.append((A[i], i))
        while 0 < len(stack): 
            bound[stack[-1][1]][1] = len(A)
            stack.pop()
        index = len(A)-1
        while 0 <= index:
            while 0 < len(stack) and A[index] < stack[-1][0]: 
                bound[stack[-1][1]][0] = index
                stack.pop()
            stack.append((A[index], index))
            index -= 1
        while 0 < len(stack): 
            bound[stack[-1][1]][0] = -1
            stack.pop()
        sum = 0
        for i in range(0, len(bound)):
            sum += A[i]*(i-bound[i][0])*(bound[i][1]-i)
            sum %= (10**9 + 7)
        return sum

class Solution:
    # def sumSubarrayMins(self, A):
    #     n, mod = len(A), 10**9 + 7
    #     left, right, s1, s2 = [0] * n, [0] * n, [], []
    #     for i in range(n):
    #         count = 1
    #         while s1 and s1[-1][0] > A[i]: count += s1.pop()[1]
    #         left[i] = count
    #         s1.append([A[i], count])
    #     for i in range(n)[::-1]:
    #         count = 1
    #         while s2 and s2[-1][0] >= A[i]: count += s2.pop()[1]
    #         right[i] = count
    #         s2.append([A[i], count])
    #     print(left)
    #     print(right)
    #     return sum(a * l * r for a, l, r in zip(A, left, right)) % mod
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        l_large = [0] * n
        l_stack = [(A[0], 0)] # mono increasing
        r_large = [0] * n
        r_stack = [(A[n-1], n-1)] # mono increasing
        for i in range(1, n):
            while l_stack and A[i] < l_stack[-1][0]:
                _, idx = l_stack.pop()
                l_large[i] = max(l_large[i], i-idx+l_large[idx])
            else: l_stack.append((A[i], i))     
            while r_stack and A[n-i-1] <= r_stack[-1][0]:
                _, idx = r_stack.pop()
                r_large[n-i-1] = max(r_large[n-i-1], idx-(n-i-1)+r_large[idx])
            else: r_stack.append((A[n-i-1], n-i-1))     
        return sum((1+l_large[i] + r_large[i] + l_large[i] * r_large[i])*A[i] for i in range(n)) % int(1000000007)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res, curr_sum, min_arr = 0, 0, [(float('-inf'),-1)]
        for i,a in enumerate(A):
            while min_arr and a < min_arr[-1][0]:
                b,j = min_arr.pop()
                curr_sum -= b*(j-min_arr[-1][1])
            curr_sum += a*(i-min_arr[-1][1])
            min_arr.append((a,i))
            res += curr_sum
        return res%(10**9+7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod = 10 ** 9 + 7
        A = [0] + A + [0]
        q = [-1]
        res = 0
        cur = 0
        
        for i, x in enumerate(A):
            while q and A[q[-1]] > x:
                cur -= A[q[-1]] * (q[-1] - q[-2])
                q.pop()
            
            res += x * (i - q[-1]) + cur
            cur += x * (i - q[-1])
            
            q.append(i)
        
        return res % mod


class Solution:
    # def sumSubarrayMins(self, A):
    #     n, mod = len(A), 10**9 + 7
    #     left, right, s1, s2 = [0] * n, [0] * n, [], []
    #     for i in range(n):
    #         count = 1
    #         while s1 and s1[-1][0] > A[i]: count += s1.pop()[1]
    #         left[i] = count
    #         s1.append([A[i], count])
    #     for i in range(n)[::-1]:
    #         count = 1
    #         while s2 and s2[-1][0] >= A[i]: count += s2.pop()[1]
    #         right[i] = count
    #         s2.append([A[i], count])
    #     print(left)
    #     print(right)
    #     return sum(a * l * r for a, l, r in zip(A, left, right)) % mod
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        l_large = [0] * n
        l_stack = [(A[0], 0)] # mono increasing
        r_large = [0] * n
        r_stack = [(A[n-1], n-1)] # mono increasing
        for i in range(1, n):
            while l_stack and A[i] <= l_stack[-1][0]:
                _, idx = l_stack.pop()
                l_large[i] = max(l_large[i], i-idx+l_large[idx])
            else: l_stack.append((A[i], i))     
            while r_stack and A[n-i-1] < r_stack[-1][0]:
                _, idx = r_stack.pop()
                r_large[n-i-1] = max(r_large[n-i-1], idx-(n-i-1)+r_large[idx])
            else: r_stack.append((A[n-i-1], n-i-1))     
        return sum((1+l_large[i] + r_large[i] + l_large[i] * r_large[i])*A[i] for i in range(n)) % int(1000000007)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        left=[1]*len(A)
        right=[1]*len(A)
        stack=[]
        for i,v in enumerate(A):
            if i==0:
                stack.append(i)
                left[i]=1
            else:
                count=1
                while stack and A[stack[-1]] >v:
                    count+=left[stack.pop()]
                left[i]=count
                stack.append(i)
        stack=[]
        for i in range(len(A)-1,-1,-1):
            count=1
            while stack and A[stack[-1]]>=A[i]:
                count+=right[stack.pop()]
            right[i]=count
            stack.append(i)
       # print(left,right)
        sum=0
        for i in range(len(A)):
            sum=sum+(left[i]*right[i]*A[i])
        return sum%1000000007

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        A = [float('-inf')] + A + [float('-inf')]
    # The -inf at the beginning makes sure that the stack is never empty. The
    # -inf at the end makes sure that every element in the original A gets
    # popped from the stack eventually.
        stack = [0]
        res = 0
        
        for i in range(1, len(A)):
            while A[i] < A[stack[-1]]:
                j = stack.pop()
                k = stack[-1]
                res += A[j] * (i - j) * (j - k)
    #eg.两个区间会有一个重合，在j， 比如j点A等于3， 这样就可算上subarray [3] 了
                res %= 10 ** 9 + 7
            stack.append(i)
        return res
        
'''
        if not A:
            return 0
        curmin = []
        res = 0
        for i in A:
            curminlevel = []
            if not curmin:
                curminlevel.append(i)
                res += i
            else:
                for j in range(len(curmin[-1])):
                    minnum = min(curmin[-1][j], i)
                    curminlevel.append(minnum)
                    res += minnum
                curminlevel.append(i)
                res += i
            curmin.append(curminlevel)
        return res%(10**9 + 7)'''
                    


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        l = len(A)
        left = [0 for _ in range(l)]
        right = [0 for _ in range(l)]
        s = []
        res = 0
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] < A[s[-1]]:
                        pre = s.pop()
                    if s == []:
                        left[i] = i
                    else:
                        left[i] = i - s[-1] - 1
                    s.append(i)
            else:
                s.append(i)
        A = A[::-1]
        s = []
        for i in range(l):
            if s:
                if A[i] > A[s[-1]]:
                    s.append(i)
                else:
                    while s and A[i] <= A[s[-1]]:
                        pre = s.pop()
                    if s == []:
                        right[i] = i
                    else:
                        right[i] = i - s[-1] -1
                    s.append(i)
            else:
                s.append(i)
        for i in range(l):
            res += A[l-1-i] * (left[i]+1) * (right[l-1-i]+1)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        
        stack = []
        mult = 0
        ans = 0
        
        for curr_val in A:
            curr_cnt = 1
            while stack and stack[-1][0] >= curr_val:
                val_p, cnt_p = stack.pop()
                curr_cnt += cnt_p
                mult -= val_p * cnt_p
            stack.append((curr_val, curr_cnt))
            mult += curr_val * curr_cnt
            ans += mult
        return ans % (10**9 + 7)
        
        
        
        
        ## Two-Pass
#         CNT = 0
#         VAL = 1
#         N = len(A)
#         left = [0] * N
#         right = [0] * N
        
#         def sum_of_single_min(idx):
#             return A[idx] * left[idx] * right[idx]
        
#         stack = []
#         for i, curr_val in enumerate(A):
#             curr_cnt = 1
#             while stack and stack[-1][VAL] > curr_val:
#                 curr_cnt += stack.pop()[CNT]
#             stack.append((curr_cnt, curr_val))
#             left[i] = curr_cnt
        
#         stack = []
#         for i in range(N-1, -1, -1):
#             curr_val = A[i]
#             curr_cnt = 1
#             while stack and stack[-1][VAL] >= curr_val:
#                 curr_cnt += stack.pop()[CNT]
#             stack.append((curr_cnt, curr_val))
#             right[i] = curr_cnt
        
#         return sum(sum_of_single_min(i) for i in range(N)) % (10**9 + 7)
        
        
        
        


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        stack = []
        bound = [[0, 0] for x in range(0, len(A))]
        for i in range(0, len(A)):
            if 0 < len(stack):
                if A[i] <= stack[-1][0]:
                    while 0 < len(stack) and A[i] <= stack[-1][0]: 
                        bound[stack[-1][1]][1] = i
                        stack.pop()
            stack.append((A[i], i))
        while 0 < len(stack): 
            bound[stack[-1][1]][1] = len(A)
            stack.pop()
        index = len(A)-1
        while 0 <= index:
            if 0 < len(stack):
                if A[index] < stack[-1][0]:
                    while 0 < len(stack) and A[index] < stack[-1][0]: 
                        bound[stack[-1][1]][0] = index
                        stack.pop()
            stack.append((A[index], index))
            index -= 1
        while 0 < len(stack): 
            bound[stack[-1][1]][0] = -1
            stack.pop()
        sum = 0
        for i in range(0, len(bound)):
            sum += A[i]*(i-bound[i][0])*(bound[i][1]-i)
            sum %= (10**9 + 7)
        return sum

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # 这道题是hulu2019年网测第二题 改成了最大值。
        # medium难度。除了暴力O(n**2) 对于每个i，右侧逐渐从i到n-1
        # 更好的办法是单调栈或者dp 时间复杂度O(n)或者O(nlogn)
        '''
        # increasing stacks,注意是subarray问题，所以是连续的一部分
        n = len(A)
        mod = 10 ** 9 + 7
        left, right = [0]*n, [0]*n
        #left[i]表示A[i]左侧，严格大于的长度
        #right[i]表示A[i]右侧，大于的长度
        #为什么，因为担心遇到连续的重复例如2，5，4，4，6 ，因此可以去掉重复部分
        #谨记，可重复出现的数组里，为了区分最小的数量，左右单调性要求不同
        s1, s2 = [], []
        for i in range(n):
            count = 1
            while s1 and s1[-1][0] > A[i]:
                count += s1.pop()[1]
            left[i] = count
            s1.append([A[i],count])
        for i in range(n)[::-1]:
            count = 1
            while s2 and s2[-1][0] >= A[i]:
                count += s2.pop()[1]
            right[i] = count
            s2.append([A[i],count])
        return sum(a*l*r for a,l,r in zip(A,left,right)) % mod
        '''
        res = 0
        s = []  # 最小值就用单调递增栈，每一个加进来的栈都是区域最小的，因为最大的被pop了
        # 递增栈的一个特点就是左右都用0最后栈会清空而且第一个0长期存在可以不用考虑stack空的问题
        A = [0] + A + [0]  # 都是大于1的数字，找最小值0没关系，反正两侧而且可以抵消因为*0
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10 ** 9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        
        # # Naive DP N^2 time, N space, over time limit
        # n = len(A)
        # md = 10**9+7
        # pre = A.copy()
        # res = sum(pre)
        # for i in range(1,n):
        #     now = [0]*(n-i)
        #     for j in range(n-i):
        #         now[j] = min(pre[j],pre[j+1])
        #         res = (res+now[j]) % md
        #     pre = now
        # return res
        
        # Copied from discussion
        res = 0
        s = []
        A = [0] + A + [0]
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int: 
        n = len(A)
        left = self.first_left_smallest(A)
        right = self.first_right_smallest(A)
        count = 0
        MOD = (10 ** 9) + 7
        for i in range(n):
            l = left[i] if left[i] != None else -1
            r = right[i] if right[i] != None else n
            n1 = i - l - 1
            n2 = r - i - 1
            num_of_sub = (n1+1)*(n2+1)
            print((i, num_of_sub))
            count += A[i] * num_of_sub
        
        return count % MOD
    
    def first_left_smallest(self, A):
        n = len(A)
        stack = []
        res = [None] * n
        for i in range(n-1, -1, -1):
            while stack and A[i] <= A[stack[-1]]:
                j = stack.pop()
                res[j] = i
            stack.append(i)
        
        return res
        
    def first_right_smallest(self, A):
        n = len(A)
        stack = []
        res = [None] * n
        for i in range(n):
            while stack and A[i] < A[stack[-1]]:
                j = stack.pop()
                res[j] = i
                
            stack.append(i)
        
        return res
            
    def brute_force(self, A):
        n = len(A)
        s = 0
        for i in range(n):
            smallest = float('inf')
            for j in range(i, n):
                smallest = min(smallest, A[j])
                s += smallest
        
        return s % (10**9 + 7)
                
                
            
    


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        pre_stack = []
        pre_val = [-1] * n
        for i,a in enumerate(A):
            while pre_stack and A[pre_stack[-1]] >= a:
                pre_stack.pop()
            if pre_stack:
                pre_val[i] = pre_stack[-1] + 1
            else:
                pre_val[i] = 0
            pre_stack.append(i)
        
        post_stack = []
        post_val = [-1] * n
        for i in range(n-1, -1, -1):
            while post_stack and A[post_stack[-1]] > A[i]:
                post_stack.pop()
            if post_stack:
                post_val[i] = post_stack[-1] - 1
            else:
                post_val[i] = n-1
            post_stack.append(i)
        
        #print(pre_val)
        #print(post_val)
        
        ans = 0
        mod_cst = 10**9 + 7
        for i in range(n):
            ans += (i - pre_val[i]+ 1) * (post_val[i] - i + 1) * A[i]
            ans %= mod_cst
        return ans
            
        
        


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # build previous less element array
        previous_less = [-1] * len(A)
        p_stack = []
        
        # build next less element array
        next_less = [-1] * len(A)
        n_stack = []
        
        for i in range(len(A)):
            n = A[i]
            # remove larger until find the smaller one
            while p_stack and A[p_stack[-1]] > n:
                p_stack.pop()
            # stack top is previous less of A[i]
            # if empty, record -1, else record stack top index
            if p_stack:
                previous_less[i] = p_stack[-1]
            else:
                previous_less[i] = -1
            p_stack.append(i)
            
            # remove larger until find the smaller one
            while n_stack and A[n_stack[-1]] > n:
                # index of the one need to be updated
                # the one that is bigger than A[i]
                x = n_stack[-1]
                n_stack.pop()
                next_less[x] = i
            n_stack.append(i)
            
        print(previous_less)
        print(next_less)
        
        ans = 0
        mod = 10 ** 9 + 7
        for i in range(len(A)):
            # calculate distance to left and right
            left = i - previous_less[i]
            
            if next_less[i] == -1:
                right = len(A) - i
            else:
                right = next_less[i] - i
            print(left)
            print(right)
            
            ans = (ans + A[i] * left * right) % mod
        return ans

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res, stack, MOD = 0, [], 10**9 + 7
        for i, x in enumerate(A):
            while stack and A[stack[-1]] >= x:
                idx = stack.pop()
                left = stack[-1] if stack else -1
                res += A[idx] * (idx - left) * (i - idx) % MOD
            stack.append(i)
        while stack:
            idx = stack.pop()
            left = stack[-1] if stack else -1
            res += A[idx] * (idx - left) * (len(A) - idx) % MOD
        return res % MOD

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        res = 0
        s = []
        A = [0] + A + [0]
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1]
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10**9 + 7)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        dp = [] 
        dp_forward = [0] * len(A) 
        dp_backward = [0] * len(A)
        for i in range(len(A)):
            while dp and A[i] < dp[-1][0]:
                dp_forward[i] += dp.pop()[1] + 1
            dp.append([A[i], dp_forward[i]])
        print(dp_forward)
        dp = []
        for i in range(len(A)-1, -1, -1):
            while dp and A[i] <= dp[-1][0]:
                dp_backward[i] += dp.pop()[1] + 1
            dp.append([A[i], dp_backward[i]])
        print(dp_backward)
        result = 0
        for i in range(len(A)):
            result += A[i]*(dp_forward[i] + 1)*(dp_backward[i] + 1)
        return result % (10**9+7)
        #return sum(a*(l+1)*(r+1) for a, l, r in zip(A, dp_forward, dp_backward)) % (10**9 + 7)


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        n = len(A)
        left = [0] * n
        right = [0] * n
        s1 = []
        s2 = []
        mod = 10 ** 9 + 7
        for i in range(n):
            cnt = 1
            while s1 and s1[-1][0] > A[i]:
                cnt += s1.pop()[1]
            s1.append((A[i], cnt))
            left[i] = cnt
        for i in range(n-1, -1, -1):
            cnt = 1
            while s2 and s2[-1][0] >= A[i]:
                cnt += s2.pop()[1]
            s2.append((A[i], cnt))
            right[i] = cnt
        return sum(A[i] * left[i] * right[i] for i in range(n)) % mod


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        prev_stack = []
        next_stack = []
        
        prev_smaller = []
        next_smaller = []
        
        for i in range(len(A)):
            prev_smaller.append(i)
            next_smaller.append(len(A) - i - 1)
        
        
        for i in range(len(A)):
            while len(next_stack) > 0 and A[next_stack[-1]] >= A[i]:
                idx = next_stack.pop()
                next_smaller[idx] = i - idx - 1
                
            next_stack.append(i)
            
            
        for i in range(len(A) - 1, -1, -1):
            while len(prev_stack) > 0 and A[prev_stack[-1]] > A[i]:
                idx = prev_stack.pop()
                prev_smaller[idx] = idx - i - 1
                
            prev_stack.append(i)
        
        m = 10 ** 9 + 7
        result = 0
        for i in range(len(A)):
            num_occurrences = (prev_smaller[i] + 1) * (next_smaller[i] + 1)
            result = (result + num_occurrences * A[i]) % m
            
        return result


# class Solution:
#     def sumSubarrayMins(self, A: List[int]) -> int:
#         MOD = 10**9+7
#         N = len(A)
        
#         stack = []
#         left, right = [None]*N, [None]*N
        
#         for i in range(N):
#             while stack and A[i]<=A[stack[-1]]:
#                 stack.pop()
#             left[i] = stack[-1] if stack else -1
#             stack.append(i)
            
#         stack = []
#         for k in range(N-1,-1,-1):
#             while stack and A[k]<A[stack[-1]]:
#                 stack.pop()
#             right[k] = stack[-1] if stack else N
#             stack.append(k)
        
#         return sum((i-left[i])*(right[i]-i)*A[i] for i in range(N)) % MOD

class Solution(object):
    def sumSubarrayMins(self, A):
        MOD = 10**9 + 7

        stack = []
        ans = dot = 0
        for j, y in enumerate(A):
            # Add all answers for subarrays [i, j], i <= j
            count = 1
            while stack and stack[-1][0] >= y:
                x, c = stack.pop()
                count += c
                dot -= x * c

            stack.append((y, count))
            dot += y * count
            ans += dot
        return ans % MOD

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        def right_boundry(A, dupl):
            res = [0] * len(A)
            A.append(-math.inf)
            stack = []
            
            for i in range(len(A)):
                if dupl:
                    while stack and A[stack[-1]] >  A[i]:
                        j = stack.pop()
                        res[j] = i - j
                else:
                    while stack and A[stack[-1]] >=  A[i]:
                        j = stack.pop()
                        res[j] = i - j
                    
                stack.append(i)
            
            A.pop()
            return res
        
        right = right_boundry(A, False)
        left = right_boundry(A[::-1], True)[::-1]
        
        ans = sum([right[i]*left[i]*A[i] for i in range(len(A))]) 
        
        return ans %(10**9+7)

    
#         dp = [0] * (len(A) + 1)
#         N = len(A)
        
#         for i in range(1,N+1):
#             mn = A[i-1]
#             dp[i] = dp[i-1]
#             for j in range(i, 0, -1):
#                 mn = min(mn, A[j-1])
#                 dp[i] = (dp[i] + mn) % (10**9 + 7)
        
#         return dp[-1]
        
        
#         cnt = 0
#         k = 1
        
#         while k <= len(A):
#             stack = []
#             for i in A:
#                 if len(stack) < k: 
#                     stack.append(i)
#                     if len(stack) == k:
#                         cnt += min(stack)
#                         stack.pop(0)
                        
#             k += 1
            
#         return cnt
                    


class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        
        larr=[-1]*len(A)
        rarr=[-1]*len(A)
        
        for i in range(len(A)):
            lefti=i-1
            while lefti>-1 and A[lefti]>A[i]:
                lefti=larr[lefti]-1
                
            larr[i]=lefti+1
            
        
        for i in range(len(A)-1,-1,-1):
            righti=i+1
            
            while righti<len(A) and A[righti]>=A[i]:
                righti=rarr[righti]+1
                
            rarr[i]=righti-1
            
        # print(larr)
        # print(rarr)
            
        count=0
        for i in range(len(A)):
            r,l=rarr[i]-i,i-larr[i]
            count+=((1+l+r+(l*r))*A[i])
            
        return count%(10**9+7)
    
    



class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        left, right = [], []
        stack = []
        for i in range(len(A)):
            count = 1
            while stack and stack[-1][0] > A[i]:
                count += stack.pop()[1]
            stack.append([A[i], count])
            left.append(count)
        stack = []
        for i in reversed(range(len(A))):
            count = 1
            while stack and stack[-1][0] >= A[i]:
                count += stack.pop()[1]
            stack.append([A[i], count])
            right.append(count)
        right = right[::-1]
        
        res = 0
        for i in range(len(A)):
            res += left[i]*right[i]*A[i]
        return res % (10**9+7)