Subarray Minimums

Problem

Given an array of integers arr, calculate the sum of the minimum value of each possible contiguous subarray. The result could be large, so return it modulo 10**9.

Examples

sumSubarrayMins([1,2,3,4])
// returns 10
// There are 10 subarrays:
// [1] (min: 1), [2] (min: 2), [3] (min: 3), [4] (min: 4),
// [1,2] (min: 1), [2,3] (min: 2), [3,4] (min: 3),
// [1,2,3] (min: 1), [2,3,4] (min: 2), [1,2,3,4] (min: 1).
// Adding up all minima gives the sum 10.

sumSubarrayMins([3,1,2]) // returns 6
sumSubarrayMins([4,2,1]) // returns 7
sumSubarrayMins([2,2,2]) // returns 12