Sum of Subarray Minimums
Given an array of integers arr, find the sum of min(b), where b ranges over every contiguous subarray of arr. Since the answer may be large, return the answer modulo 10^9 + 7.
Example 1
Input
arr = [3,1,2,4]Output
17The subarray minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, and 1, whose sum is 17.
Example 2
Input
arr = [11,81,94,43,3]Output
444The sum of the minimum values over all contiguous subarrays is 444.
Constraints
- 1 <= arr.length <= 3 * 10^4
- 1 <= arr[i] <= 3 * 10^4