<p>You are given an integer array <code>nums</code>. The <strong>range</strong> of a subarray of <code>nums</code> is the difference between the largest and smallest element in the subarray.</p>

<p>Return <em>the <strong>sum of all</strong> subarray ranges of </em><code>nums</code><em>.</em></p>

<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0 
[2], range = 2 - 2 = 0
[3], range = 3 - 3 = 0
[1,2], range = 2 - 1 = 1
[2,3], range = 3 - 2 = 1
[1,2,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 1 + 1 + 2 = 4.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,3]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The 6 subarrays of nums are the following:
[1], range = largest - smallest = 1 - 1 = 0
[3], range = 3 - 3 = 0
[3], range = 3 - 3 = 0
[1,3], range = 3 - 1 = 2
[3,3], range = 3 - 3 = 0
[1,3,3], range = 3 - 1 = 2
So the sum of all ranges is 0 + 0 + 0 + 2 + 0 + 2 = 4.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,-2,-3,4,1]
<strong>Output:</strong> 59
<strong>Explanation:</strong> The sum of all subarray ranges of nums is 59.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>-10<sup>9</sup> &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow-up:</strong> Could you find a solution with <code>O(n)</code> time complexity?</p>

class Solution {
public:

    void findNSE(vector<int>& arr, int dir, int *res){
        // dir == 0 for left and 1 for right;
        int n = arr.size();
        stack <int> st;
        if(dir==0){
            for(int i=0; i<n; i++){
                while(!st.empty() &&  arr[st.top()] > arr[i])
                    st.pop();
                if(!st.empty()) res[i] = st.top();
                st.push(i);
            }
        }
        else{
            for(int i=n-1; i>=0; i--){
                while(!st.empty() &&  arr[st.top()] >= arr[i])
                    st.pop();
                if(!st.empty()) res[i] = st.top();
                st.push(i);
            }

        }
    }
    void findNGE(vector<int>& arr, int dir, int *res){
        int n = arr.size();
        stack<int> st;
        if(dir==0){
            for(int i=0; i<n; i++){
                while(!st.empty() &&  arr[st.top()] < arr[i])
                    st.pop();
                if(!st.empty()) res[i] = st.top();
                st.push(i);
            }
        }
        else{
            for(int i=n-1; i>=0; i--){
                while(!st.empty() &&  arr[st.top()] <= arr[i])
                    st.pop();
                if(!st.empty()) res[i] = st.top();
                st.push(i);
            }

        }
    }

    long long findLargestSum(vector<int>& arr){
        int n= arr.size();
        int ngr[n], ngl[n];
        
        fill(ngr, ngr+n, n);
        fill(ngl, ngl+n, -1);

        findNGE(arr, 0, ngl);
        findNGE(arr, 1, ngr);

        long long sum = 0;
        for(int i=0; i<n; i++){
            sum += ((1LL* (i-ngl[i]) * (ngr[i]-i))*arr[i]);
        }

        return sum;

    }
    long long findSmallestSum(vector<int>& arr){
        int n = arr.size();
        int nsr[n], nsl[n];
        fill(nsr, nsr+n, n);
        fill(nsl, nsl+n, -1);

        findNSE(arr, 0, nsl);
        findNSE(arr, 1, nsr);
        long long sum = 0;
        for(int i=0; i<n; i++){
            sum +=  ((1LL* (i-nsl[i]) * (nsr[i]-i))*arr[i]);
        }

        return sum;

    }
    long long subArrayRanges(vector<int>& nums) {
        return findLargestSum(nums)-findSmallestSum(nums);
    }
};
13700