<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:
    /*
        Denote by left[i] the distance between element A[i] and its PSE.
        Denote by right[i] the distance between element A[i] and its NGE.

        The final answer is,
        sum(A[i]*left[i]*right[i] )

        The last thing that needs to be mentioned for handling duplicate
       elements: Method: Set strict less and non-strict less(less than or equal
       to) for finding NLE and PLE respectively. The order doesn't matter.

        For example, the below code for finding NLE is strict less, while PLE is
       actually non-strict less. Remark: Although in both loop conditions the
       signs are set as >, for NGE, we make records inside the loop, while for
       PSE, records are done outside the loop.

    */

    int sumSubarrayMins(vector<int>& A) {

        int n = A.size();
        int MOD = 1e9 + 7;
        vector<int> left(n), right(n);

        // for every i find the Previous smaller element to left and next
        // greater element to 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;
    }
};
45500