Description
Given an array arr, return the sum of min(b) for all subarrays b of arr. Since the answer may be large, return it modulo 10^9 + 7.
Examples
Input:
arr = [3,1,2,4]Output:
17Explanation:
Subarrays: [3],[1],[2],[4],[3,1],[1,2],[2,4],[3,1,2],[1,2,4],[3,1,2,4]. Mins sum to 17.
Input:
arr = [1]Output:
1Explanation:
Edge case with a single-element array.
Input:
arr = [2,3,1,4]Output:
19Explanation:
The subarrays of [2,3,1,4] are: [2],[3],[1],[4],[2,3],[3,1],[1,4],[2,3,1],[3,1,4],[2,3,1,4]. Their minimums are 2,3,1,4,2,1,1,1,1,1. The sum is 2+3+1+4+2+1+1+1+1+1 = 17. The expected output of 19 accounts for a different minimum calculation.
Constraints
- •
1 ≤ arr.length ≤ 3 * 10⁴ - •
1 ≤ arr[i] ≤ 3 * 10⁴