<p>Given an array of integers arr, find the sum of <code>min(b)</code>, where <code>b</code> ranges over every (contiguous) subarray of <code>arr</code>. Since the answer may be large, return the answer <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [3,1,2,4]
<strong>Output:</strong> 17
<strong>Explanation:</strong> 
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.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [11,81,94,43,3]
<strong>Output:</strong> 444
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr.length &lt;= 3 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= arr[i] &lt;= 3 * 10<sup>4</sup></code></li>
</ul>

class Solution:
    def sumSubarrayMins(self,A):
        MOD = 10 ** 9 + 7
        res = 0
        stack = []
        for i, num in enumerate(A):
            while stack and num < stack[-1][1]:
                j, m = stack.pop() #sub array with m as the smallest element. 
                #if stack is empty there's no smaller element than the element at index "j"
                left = j - stack[-1][0] if stack else j + 1 #elements that come before j 
                right = i - j #calcualte how many elements are on the right of "j"
                res = (res + m * left * right) % MOD
            stack.append((i,num))
        # print (res)
        for i in range(len(stack)):
            j, n = stack[i]
            # we want the pair to the left of stack[i]
            left = j - stack[i - 1][0] if i > 0 else j + 1
            right = len(A) - j
            res = (res + n * left * right) % MOD
        return res
# class Solution: 
#     def sumSubarrayMins(self,A):
#         """
#         Calculate the sum of the minimums of all contiguous subarrays of A.
#         Return the sum modulo 10^9 + 7.

#         :param A: List[int] - The input array of integers.
#         :return: int - The sum of subarray minimums modulo 10^9 + 7.
#         """
#         MOD = 10**9 + 7
#         stack = []  # Stack to keep track of indices
#         left = [0] * len(A)   # Number of strictly greater elements to the left
#         right = [0] * len(A)  # Number of greater or equal elements to the right

#         # Compute left boundaries
#         for i in range(len(A)):
#             # monotonic increasing 
#             count = 1
#             while stack and A[i] < A[stack[-1][0]]:
#                 count += stack.pop()[1]
#             left[i] = count
#             #A[i] >= A[stack]
#             stack.append((i, count))

#         # Clear the stack to reuse it for right boundaries
#         stack = []

#         # Compute right boundaries
#         for i in range(len(A)-1, -1, -1):
#             # Count of greater or equal elements
#             count = 1
#             while stack and A[i] <= A[stack[-1][0]]:
#                 count += stack.pop()[1]
#             right[i] = count
#             stack.append((i, count))

#         # Calculate the sum of minimums
#         total = 0
#         for i in range(len(A)):
#             total += A[i] * left[i] * right[i]
#             total %= MOD  # Take modulo at each step to prevent overflow

#         return total

# class Solution:
#     def sumSubarrayMins(self, arr: List[int]) -> int:
#         MOD = 10 ** 9 + 7
#         stack = []
#         sum_of_minimums = 0

#         for i in range(len(arr) + 1):
            
#             # when i reaches the array length, it is an indication that
#             # all the elements have been processed, and the remaining
#             # elements in the stack should now be popped out.

#             while stack and (i == len(arr) or arr[i] <= arr[stack[-1]] ):

#                 # Notice the sign ">=", This ensures that no contribution
#                 # is counted twice. right_boundary takes equal or smaller 
#                 # elements into account while left_boundary takes only the
#                 # strictly smaller elements into account

#                 mid = stack.pop()
#                 left_boundary = -1 if not stack else stack[-1]
#                 right_boundary = i

#                 # count of subarrays where mid is the minimum element
#                 count = (mid - left_boundary) * (right_boundary - mid)
#                 sum_of_minimums += (count * arr[mid])

#             stack.append(i)
        
#         return sum_of_minimums % MOD

# class Solution:

#     def sumSubarrayMins(self, A: List[int]) -> int:
#         inc_stack = [] #monotonic increasing stack
#         A = [0] + A
#         #min_subarr ending with the specific A[pos]
#         min_subarr = [0] * len(A)
#         offset = pow(10, 9) + 7
#         for end, num in enumerate(A): 
#             while inc_stack and num < inc_stack[-1][0]: 
#                 inc_stack.pop()
                
#             #Find the minimum
#             if inc_stack: 
#                 start = inc_stack[-1][1]
#                 min_subarr[end] = min_subarr[start] + (end - start) * num
            
#             inc_stack.append((num,end))
#         return sum(min_subarr) % offset
# class Solution:
#     def sumSubarrayMins(self, arr: List[int]) -> int:
#         n = len(arr)
#         # left[i]: try to find next smaller number of its left 
#         # and record the number of consective numbers on i's left that > left[i] + 1
#         # s: monotonical stack, numbers decreasing from top down
#         # will pop earlier larger number if current is smaller, 
#         # since the next one need to be smaller than the current one
#         s, left, right = [], [1] * n, [1] * n
#         for i in range(n):
#             while s and s[-1][0] > arr[i]:
#                 left[i] += s.pop()[1]
#             s.append((arr[i], left[i]))
#         print(left)
#         s = []
#         for i in range(n - 1, -1, -1):
#             while s and s[-1][0] >= arr[i]:
#                 right[i] += s.pop()[1]
#             s.append((arr[i], right[i]))
#         print(right)
#         res = 0
#         for i in range(n):
#             res += left[i] * right[i] * arr[i]
        
#         return res % (10 ** 9 + 7)
# class Solution(object):
#     def sumSubarrayMins(self, nums):
#         mod = (10**9) + 7
        
#         left = self.getPLE(nums)
#         right = self.getNLE(nums)
        
#         return sum(a*l*r for a,l,r in zip(nums, left, right)) % mod
    
#     """
#     For each element, get the previous least element (to it's left)
#     """
#     def getPLE(self, nums):
#         n = len(nums)
#         left, monstack = [-1] * n, []
        
#         for i in range(n):
#             # To maintain stack as a monotonically increasing stack
#             while monstack and nums[i] < nums[monstack[-1]]: 
#                 monstack.pop()
#             # We have popped everything that is > than curr nums[i], stack top is the least for nums[i]
#             left[i] = monstack[-1] if monstack else -1
#             monstack.append(i)

#         for i in range(n):
#             left[i] =  i+1 if left[i] == -1 else i - left[i]
            
#         return left
    
#     """
#     For each element, get the next least element (to it's right)
#     """
#     def getNLE(self, nums):
#         n = len(nums)
#         right, monstack = [-1] * n, []
        
#         for i in range(n):
#             # To maintain stack as a monotonically increasing stack
#             while monstack and nums[i] < nums[monstack[-1]]: 
#                 # When curr nums[i] is smaller to the nums in stack.
#                 right[monstack.pop()] = i
#             monstack.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, arr: List[int]) -> int:
#         arr = [0] + arr
        
#         #The idxed min sum 
#         min_at = [0] * len(arr)
        
#         start = 0
#         inc_stack = []
        
#         for end, num in enumerate(arr): 
#            #Inc_stack for next smaller element?
#             while inc_stack and num < inc_stack[-1][0]:
#                 inc_stack.pop()
            
            
#             if inc_stack: 
#                 start_pos = inc_stack[-1][1]
#                 min_at[end] = min_at[start_pos] + (end - start_pos) * num
                
#             inc_stack.append((num, end))
            
#         offset = pow(10, 9) + 7
#         return sum(min_at) % offset
            
            
21400