You are given an integer array nums. The range of a subarray of nums is the difference between the largest and smallest element in the subarray.

Return the sum of all subarray ranges of nums.

A subarray is a contiguous non-empty sequence of elements within an array.

&nbsp;
Example 1:

Input: nums = [1,2,3]
Output: 4
Explanation: 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.

Example 2:

Input: nums = [1,3,3]
Output: 4
Explanation: 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.


Example 3:

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


&nbsp;
Constraints:


	1 &lt;= nums.length &lt;= 1000
	-109 &lt;= nums[i] &lt;= 109


&nbsp;
Follow-up: Could you find a solution with O(n) time complexity?

class Solution:
    def subArrayRanges(self, nums: List[int]) -> int:
        n = len(nums)
        
        # the answer will be sum{ Max(subarray) - Min(subarray) } over all possible subarray
        # which decomposes to sum{Max(subarray)} - sum{Min(subarray)} over all possible subarray
        # so totalsum = maxsum - minsum
        # we calculate minsum and maxsum in two different loops
        minsum = maxsum = 0
        
        # first calculate sum{ Min(subarray) } over all subarrays
        # sum{ Min(subarray) } = sum(f(i) * nums[i]) ; i=0..n-1
        # where f(i) is number of subarrays where nums[i] is the minimum value
        # f(i) = (i - index of the previous smaller value) * (index of the next smaller value - i) * nums[i]
        # we can claculate these indices in linear time using a monotonically increasing stack.
        stack = []
        for next_smaller in range(n + 1):
			# we pop from the stack in order to satisfy the monotonically increasing order property
			# if we reach the end of the iteration and there are elements present in the stack, we pop all of them
            while stack and (next_smaller == n or nums[stack[-1]] > nums[next_smaller]):
                i = stack.pop()
                prev_smaller = stack[-1] if stack else -1
                minsum += nums[i] * (next_smaller - i) * (i - prev_smaller)
            stack.append(next_smaller)
            
        # then calculate sum{ Max(subarray) } over all subarrays
        # sum{ Max(subarray) } = sum(f'(i) * nums[i]) ; i=0..n-1
        # where f'(i) is number of subarrays where nums[i] is the maximum value
        # f'(i) = (i - index of the previous larger value) - (index of the next larger value - i) * nums[i]
        # this time we use a monotonically decreasing stack.
        stack = []
        for next_larger in range(n + 1):
			# we pop from the stack in order to satisfy the monotonically decreasing order property
			# if we reach the end of the iteration and there are elements present in the stack, we pop all of them
            while stack and (next_larger == n or nums[stack[-1]] < nums[next_larger]):
                i = stack.pop()
                prev_larger = stack[-1] if stack else -1
                maxsum += nums[i] * (next_larger - i) * (i - prev_larger)
            stack.append(next_larger)
        
        return maxsum - minsum
class Solution {
    class Node{
        long val, displace;
        Node(long val, long displace){
            this.val = val;
            this.displace = displace;
        }
    }
    public long subArrayRanges(int[] nums) {
        
        //lesser than current element
        Stack<Node> stack = new Stack<>();
        //from left
        long [] lesserLeft = new long[nums.length];
        for (int i = 0; i< nums.length; i++){
            long count = 1;
            while(stack.size()>0 && stack.peek().val<=nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            lesserLeft[i] = count;
        }
        stack.clear();
        //from right
        long[] lesserRight = new long[nums.length];
        for (int i = nums.length-1; i>=0; i--){
            long count = 1;
            while(stack.size()>0 && stack.peek().val<nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            lesserRight[i] = count;
        }
        
        
        //greater than current element
        stack.clear();
        //from left
        long [] greaterLeft = new long[nums.length];
        for (int i = 0; i< nums.length; i++){
            long count = 1;
            while(stack.size()>0 && stack.peek().val>=nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            greaterLeft[i] = count;
        }
        stack.clear();
        //from right
        long[] greaterRight = new long[nums.length];
        for (int i = nums.length-1; i>=0; i--){
            long count = 1;
            while(stack.size()>0 && stack.peek().val>nums[i]){
                count+=stack.pop().displace;
            }
            stack.add(new Node(nums[i], count));
            greaterRight[i] = count;
        }        
        
        long ans = 0;
        //Now we subtract the count of minimum occurrences from the count of maximum occurrences
        
        for (int i = 0; i< nums.length; i++){
            ans+=((lesserLeft[i]*lesserRight[i]) - (greaterLeft[i]*greaterRight[i]))*nums[i];
        }
        return ans;
    }
}
class Solution {
public:
    long long subArrayRanges(vector<int>& nums) {
        int n=nums.size();
        long long res=0;
        for(int i=0;i<n-1;i++){
            int maxi=nums[i], mini=nums[i];
            for(int j=i+1;j<n;j++){
                if(nums[j]>maxi)maxi=nums[j];
                else if(nums[j]<mini)mini=nums[j];
                res+=maxi-mini;
            }
        }
        return res;
    }
};
// O(n^3) time | O(1) space
var subArrayRanges = function(nums) {
    let res = 0
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            let smallest = nums[i], biggest = nums[i]
            for (let k = j; k < i; k++) {
                smallest = Math.min(smallest, nums[k])
                biggest = Math.max(biggest, nums[k])
            }
            res += biggest - smallest
        }
    }
    return res
};
Sum of Subarray Ranges