All problems

Sum of Subarray Minimums

Medium · stack

You are given a list of positive integers nums. A subarray is a non-empty run of neighbouring elements, such as nums[2..5]. Two subarrays are different if they start or end at different positions, even when they hold the same values.

Take the smallest value in every subarray and add all those minimums together. Because the total can be huge, return it modulo 1000000007 (that is, 10^9 + 7).

Examples

Example 1

Input: nums = [2, 5, 2]

Output: 15

The six subarrays have minimums 2, 5, 2 (single elements), 2, 2 (the two pairs) and 2 (the whole list). They add up to 15.

Example 2

Input: nums = [7]

Output: 7

Example 3

Input: nums = [4, 4, 4]

Output: 24

All six subarrays have minimum 4, and 6 times 4 is 24. Equal values still make different subarrays.

Constraints