Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

&nbsp;
Example 1:

Input: arr = [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.


Example 2:

Input: arr = [11,81,94,43,3]
Output: 444


&nbsp;
Constraints:


	1 &lt;= arr.length &lt;= 3 * 104
	1 &lt;= arr[i] &lt;= 3 * 104


class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        small_before = [-1]*n
        stack = []
        for i in range(n):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()
            if stack:small_before[i] = stack[-1]
            stack.append(i)
        best = [0]*(n+1)
        ans = 0
        for i in range(n):
            best[i] = best[small_before[i]] + (i - small_before[i])*arr[i]
            ans += best[i]
        return ans%1000000007
class Solution {
    public int sumSubarrayMins(int[] arr) {
      int n = arr.length;
      int ans1[] = nsl(arr);
      int ans2[] = nsr(arr);
      long sum=0;
      for(int i=0;i<n;i++){
        sum=(sum + (long)(arr[i]*(long)(ans1[i]*ans2[i])%1000000007)%1000000007)%1000000007;
      }
      return (int)sum;
	}
    public static int[] nsl(int arr[]){
      Stack<Integer> s = new Stack<>();
      int ans[] = new int[arr.length];
      for(int i=0;i<arr.length;i++){
        while(!s.isEmpty() && arr[i]<arr[s.peek()]){
          s.pop();
        }
        if(s.isEmpty()){
          ans[i] = i-(-1);
          s.push(i);
        }
        else{
          ans[i] = i-s.peek();
          s.push(i);
        }
      }
      return ans;
    }
  public static int[] nsr(int arr[]){
      Stack<Integer> s = new Stack<>();
      int ans[] = new int[arr.length];
      for(int i=arr.length-1;i>=0;i--){
        while(!s.isEmpty() && arr[s.peek()]>=arr[i]){
          s.pop();
        }
        if(s.isEmpty()){
          ans[i] = arr.length-i;
          s.push(i);
        }
        else{
          ans[i] = s.peek()-i;
          s.push(i);
        }
      }
      return ans;
    }
}
class Solution {
public: //Thanks to Bhalerao-2002
    int sumSubarrayMins(vector<int>& A) {
        
        int n = A.size();
        int MOD = 1e9 + 7;
        vector<int> left(n), right(n);
        
        // for every i find the Next smaller element to left and right
        
        // Left
        stack<int>st;
        st.push(0);
        left[0] = 1; // distance = 1, left not found, this is distance multiplied with num, so it can't be zero
        for(int i=1; i<n; i++)
        {
            while(!st.empty() && A[i] < A[st.top()]) 
                st.pop();
            
            if(st.empty()) 
                left[i] = i+1; // total distance if less element not found = i+1
            else 
                left[i] = i - st.top(); // distance = i-st.top()
            
            st.push(i);
            
        }
        
        while(st.size()) 
            st.pop();
        
        // Right 
        st.push(n-1);
        right[n-1] = 1; // distance = 1, right not found, this is distance multiplied with num, so it can't be zero
        for(int i=n-2; i>=0; i--)
        {
            while(!st.empty() && A[i] <= A[st.top()]) 
                st.pop();
            
            if(st.empty()) 
                right[i] = n-i; // distance
            else 
                right[i] = st.top()-i;
            
            st.push(i);
        }
        
        // total number of subarrays : (Left[i] * Right[i])
        // total contribution in A[i] element in final answer : (Left * Right) * A[i] 
        
        for(int i=0; i<n; i++) 
             cout << left[i] << " : " << right[i] << endl;
        
        // for each i, contribution is (Left * Right) * Element 
        
        int res = 0;
        for(int i=0; i<n; i++)
        {
            long long prod = (left[i]*right[i])%MOD;
            prod = (prod*A[i])%MOD;
            res = (res + prod)%MOD;
        }
        
        return res%MOD;
    }
    

};
var sumSubarrayMins = function(arr) {
    
    M = 10**9+7
    stack = [-1]
    res = 0
    arr.push(0)
    
    for(let i2 = 0; i2 < arr.length; i2++){
        while(arr[i2] < arr[stack[stack.length -1]]){
            i = stack.pop()
            i1 = stack[stack.length-1]
            Left = i - i1
            Right = i2 -i
            res += (Left*Right*arr[i])
        };
        stack.push(i2)
    };
    
    return res%M
};
Sum of Subarray Minimums