Sum of Subarray Minimums

A subarray is a run of one or more neighbouring items from a list. Write sum_of_minimums(nums) that looks at every subarray of nums, takes the smallest value in each one, and returns the total of all those minimums.

Examples

sum_of_minimums([2, 4, 1])  # returns 11
sum_of_minimums([5, 5])     # returns 15
sum_of_minimums([1, 2, 3])  # returns 10
sum_of_minimums([])         # returns 0

For [2, 4, 1] the subarrays are [2], [4], [1], [2, 4], [4, 1] and [2, 4, 1]. Their minimums are 2, 4, 1, 2, 1 and 1, which add up to 11.

Constraints

• 0 <= len(nums) <= 30,000
• -10,000 <= nums[i] <= 10,000
• A list of 30,000 items has about 450 million subarrays, so visiting them one by one is far too slow.