Sum of Subarray Spreads

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

Return the sum of the spreads of every subarray of nums.

A subarray is a contiguous, non-empty sequence of elements within nums.

Note that the answer can exceed the 32-bit integer range.

Examples

Example 1

Input: nums = [1,2,3]
Output: 4
Explanation: The six subarrays are [1] (spread 0), [2] (spread 0), [3] (spread 0), [1,2] (spread 1), [2,3] (spread 1) and [1,2,3] (spread 2). The total is 0 + 0 + 0 + 1 + 1 + 2 = 4.

Example 2

Input: nums = [1,3,3]
Output: 4
Explanation: The six subarrays are [1] (spread 0), [3] (spread 0), [3] (spread 0), [1,3] (spread 2), [3,3] (spread 0) and [1,3,3] (spread 2). The total is 0 + 0 + 0 + 2 + 0 + 2 = 4.

Example 3

Input: nums = [4,-2,-3,4,1]
Output: 59
Explanation: Summing the spread of every one of the fifteen subarrays of nums gives 59.