<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:

// next smaller elements ...
vector<int> nse(vector<int> &arr)
{
    int n = arr.size();
    stack<int> st;
    vector<int> ans;

    for (int i = n - 1; i >= 0; i--)
    {
        if (ans.size() == 0)
            ans.push_back(n);
        else if (ans.size() > 0 and !st.empty())
        {
            if (arr[i] > arr[st.top()])
                ans.push_back(st.top());
            else
            {
                // if arr[i] < arr[st.top()] ...
                while (!st.empty() and arr[i] <= arr[st.top()])
                    st.pop();

                if (st.empty())
                    ans.push_back(n);
                else
                    ans.push_back(st.top());
            }
        }
        st.push(i);
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

// previous smaller equal elements ...
vector<int> pseqe(vector<int> &arr)
{
    int n = arr.size();
    stack<int> st;
    vector<int> ans;

    for (int i = 0; i < n; i++)
    {
        if (ans.size() == 0)
            ans.push_back(-1);
        else if (ans.size() > 0 and !st.empty())
        {
            if (arr[i] >= arr[st.top()])
                ans.push_back(st.top());
            else
            {
                // arr[i] < arr[st.top()]  ...
                while (!st.empty() and arr[i] < arr[st.top()])
                    st.pop();

                if (st.empty())
                    ans.push_back(-1);
                else
                    ans.push_back(st.top());
            }
        }
        st.push(i);
    }

    return ans;
}


int sumSubarrayMins(vector<int> &arr)
{
    int n = arr.size();
    int sum = 0, MOD = 1e9 + 7;

    vector<int> nexsml = nse(arr);
    vector<int> prevsmleq = pseqe(arr);

    for(auto it : nexsml)cout<<it<<" ";
    cout<<endl;
    for(auto it : prevsmleq)cout<<it<<" ";
    cout<<endl;

    for (int i = 0; i < n; i++)
    {
        int right = nexsml[i] - i;
        int left = i - prevsmleq[i];

        sum += (static_cast<long long>(left) * (right)*arr[i] % MOD) % MOD;
        sum %= MOD;
    }

    return sum;
}
};
49300