Sum of Subarray Minimums

1. Understand the Contribution Approach

• Instead of iterating over all O(n²) subarrays, we ask: for each element arr[i], how many subarrays have arr[i] as their minimum?
• If arr[i] is the minimum of a subarray, it contributes arr[i] to the total sum for that subarray.
• So the total contribution of arr[i] is arr[i] × (number of subarrays where arr[i] is the minimum).

2. Find Previous Less Element (PLE)

• Use a monotonic increasing stack scanning left to right.
• For each index i, find the nearest index to the left where the element is strictly less than arr[i].
• If no such index exists, set prevLess[i] = -1 (meaning the boundary extends to the start of the array).

3. Find Next Less or Equal Element (NLE)

• Use a monotonic increasing stack scanning right to left.
• For each index i, find the nearest index to the right where the element is less than or equal to arr[i].
• If no such index exists, set nextLess[i] = n (meaning the boundary extends to the end of the array).
• Using strictly less on the left and less or equal on the right prevents double-counting when there are duplicate values.

4. Calculate Each Element's Contribution

• The number of subarrays where arr[i] is the minimum equals left × right, where:
• left = i - prevLess[i] — the number of choices for the left boundary
• right = nextLess[i] - i — the number of choices for the right boundary
• Add arr[i] × left × right to the running total, taking modulo 10^9 + 7.

5. Return the Result

• After processing all elements, return the accumulated sum modulo 10^9 + 7.

Key Insight

The monotonic stack lets us efficiently find how far each element can "extend" as the minimum in both directions. By computing left × right for each element, we count the exact number of subarrays where that element is the minimum — turning an O(n²) brute-force into an elegant O(n) time, O(n) space solution. The asymmetry (strict less on left, less-or-equal on right) is critical for correctly handling duplicate values.