Given an array nums of positive integers, consider every non-empty contiguous subarray of nums and take the minimum element of each. Return the sum of all those minimums.
The sum can be very large; return it modulo 109+7.
Examples
Example 1
Input: nums = [3,1,2,4]
Output: 17
Explanation: The 10 subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4], with minimums 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Their sum is 17.
Example 2
Input: nums = [11,81,94,43,3]
Output: 444
Constraints
1≤nums.length≤3⋅104
1≤nums[i]≤3⋅104
Examples
Example 1
Input
nums = [3, 1, 2, 4]
Output
17
Example 2
Input
nums = [11, 81, 94, 43, 3]
Output
444
Loading editor...
Click "Run" to test with sample cases or "Submit" to run all tests.