Problem Statement

Given an integer array arr, find the sum of the minimum elements of all possible subarrays of arr. Return the answer modulo 10^9 + 7 as it may be very large.

Examples

Example 1:

• Input: [2, 3, 1]
• Expected Output: 10
• Justification: The subarrays are [2], [3], [1], [2, 3], [3, 1], and [2, 3, 1]. Their minimums are 2, 3, 1, 2, 1, and 1 respectively. Summing these minimums yields 10.

Example 2:

• Input: [4, 5, 2]
• Expected Output: 19
• Justification: The subarrays are [4], [5], [2], [4, 5], [5, 2], and [4, 5, 2]. Their minimums are 4, 5, 2, 4, 2, and 2 respectively. Summing these minimums gives us 19.

Example 3:

• Input: [7, 2, 8, 4]
• Expected Output: 35
• Justification: The subarrays are [7], [2], [8], [4], [7, 2], [2, 8], [8, 4], [7, 2, 8], [2, 8, 4], and [7, 2, 8, 4]. Their minimums are 7, 2, 8, 4, 2, 2, 4, 2, 2, and 2 respectively. Summing these minimums totals 35.

Try it yourself

Try solving this question here: