1#include <stdio.h>
2#define MOD 1000000007
3#define MAX 30000
4
5int sumSubarrayMins(int* arr, int arrSize) {
6    long res = 0;
7    int stack[MAX], top = -1;
8    int left[MAX], right[MAX];
9    
10    for (int i = 0; i < arrSize; ++i) {
11        while (top != -1 && arr[stack[top]] > arr[i]) --top;
12        left[i] = (top == -1) ? i + 1 : i - stack[top];
13        stack[++top] = i;
14    }
15    
16    top = -1;
17    for (int i = arrSize - 1; i >= 0; --i) {
18        while (top != -1 && arr[stack[top]] >= arr[i]) --top;
19        right[i] = (top == -1) ? arrSize - i : stack[top] - i;
20        stack[++top] = i;
21    }
22    
23    for (int i = 0; i < arrSize; ++i) {
24        res = (res + (long)arr[i] * left[i] * right[i]) % MOD;
25    }
26    
27    return (int)res;
28}

1#include <vector>
#include <stack>
using namespace std;

typedef long long ll;

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int MOD = 1e9 + 7;
        int n = arr.size();
        vector<int> dp(n);
        stack<int> s;
        ll result = 0;

        for (int i = 0; i < n; ++i) {
            while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
            int k = (s.empty()) ? i + 1 : i - s.top();
            dp[i] = (arr[i] * k + (s.empty() ? 0 : dp[s.top()])) % MOD;
            result = (result + dp[i]) % MOD;
            s.push(i);
        }

        return (int)result;
    }
};