<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 {
public:
    stack<int>ns;
    stack<int>ps;
    
    
    void NextSmallerElement(vector<int>& arr,vector<int>&nse) //store next smaller index
    {
        for(int i = arr.size()-1 ;i>=0;i--)
        {
            while(!ns.empty() && arr[ns.top()] >= arr[i])
            {
               ns.pop(); 
            }
            if(!ns.empty())
            {
                nse[i] = ns.top();
            }
            ns.push(i);
        }
    }

    // void PrevSmallerElement(vector<int>& arr,vector<int>&pse) // prev smaller index
    // {
    //     for(int i=0;i<arr.size();i++)
    //     {
    //         while(!ps.empty() && arr[ps.top()] > arr[i])
    //         {
    //            ps.pop(); 
    //         }
    //         if(!ps.empty())
    //         {
    //             pse[i] = ps.top();
    //         }
    //         ps.push(i);
    //     }   
    // }

    int sumSubarrayMins(vector<int>& arr) {
       int n = arr.size();
       vector<int>nse(n,n);        
       NextSmallerElement(arr,nse);
   

       long contribution =0;
       long modulo = 1e9+7;
       int pse =-1;
       for(int i=0;i<n;i++)
       {
     
            while(!ps.empty() && arr[ps.top()] > arr[i])
            {
               ps.pop(); 
            }
            int pse = ps.empty() ? -1 : ps.top();
            ps.push(i);
         int left = i - pse;
         int right = nse[i] - i;
         contribution += (left * right % modulo * arr[i] % modulo) % modulo;
         contribution %= modulo;
       }
       return contribution;      
    }
};
44400