Sum of Subarray Ranges

Given an integer array nums, return the sum of all subarray ranges.

The range of a subarray is the difference between the largest and smallest elements in the subarray. A subarray is a contiguous non-empty sequence of elements within the array.

Examples

Input: nums = [1,2,3]

Output: 4

Explanation: The 6 subarrays are:

• [1], range = 0
• [2], range = 0
• [3], range = 0
• [1,2], range = 2 - 1 = 1
• [2,3], range = 3 - 2 = 1
• [1,2,3], range = 3 - 1 = 2

Sum of ranges = 0 + 0 + 0 + 1 + 1 + 2 = 4.

Input: nums = [1,3,3]

Output: 4

Explanation: The 6 subarrays are:

• [1], range = 0
• [3], range = 0
• [3], range = 0
• [1,3], range = 2
• [3,3], range = 0
• [1,3,3], range = 2

Sum of ranges = 0 + 0 + 0 + 2 + 0 + 2 = 4.

Input: nums = [4,-2,-3,4,1]

Output: 59

Explanation: The sum of all subarray ranges in the array is 59.

Constraints

• 1 <= nums.length <= 1000
• -10^9 <= nums[i] <= 10^9