Sum the Minimum Value of Every Contiguous Subarray
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
For every nonempty contiguous subarray of `arr`, take its minimum. Return the sum of those minimums modulo `10^9+7`.
```cpp
class Solution {
public:
int sumSubarrayMins(vector<int>& arr);
};
```
### Examples
**Example 1:**
```text
Input: arr = [2,2]
Output: 6
Explanation: The two singleton minimums and the two-element minimum are all2, totaling6.
```
**Example 2:**
```text
Input: arr = [4,1,3]
Output: 11
Explanation: Singleton minimums sum to8, both length-two minimums are1, and the full-array minimum is1.
```
### Constraints
- `1 <= arr.length <= 3*10^4`.
- `1 <= arr[i] <= 3*10^4`.
### Contract considerations
Subarrays are distinguished by their index intervals, so equal-valued subarrays still contribute separately.
```hint Read the boundary condition
Count how many subarrays choose one particular occurrence as their rightmost minimum.
```
### Boundary reminders
Subarrays are distinguished by their index intervals, so equal-valued subarrays still contribute separately.
Overview: Sum the Minimum Value of Every Contiguous Subarray. For every nonempty contiguous subarray of arr, take its minimum.
