<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, arr: List[int]) -> int:
        stack = []
        Mod = 10**9 + 7
        ans = 0
        n = len(arr)

        for right in range(n + 1):
            while stack and (right == n or arr[stack[-1]] >= arr[right]):
                element = stack.pop()
                left = -1 if not stack else stack[-1]
                ans += arr[element] * (element - left) * (right - element)
        
            stack.append(right)
        
        return ans%Mod





















        # 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[stack[-1]] >= arr[i]):

        #         # 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
21400