1#include <vector>
2#include <stack>
3using namespace std;
4
5typedef long long ll;
6class Solution {
7public:
8    int sumSubarrayMins(vector<int>& arr) {
9        const ll MOD = 1e9 + 7;
10        int n = arr.size();
11        vector<int> left(n), right(n);
12        stack<int> s1, s2;
13        
14        for (int i = 0; i < n; i++) {
15            while (!s1.empty() && arr[s1.top()] > arr[i]) s1.pop();
16            left[i] = (s1.empty()) ? (i + 1) : (i - s1.top());
17            s1.push(i);
18        }
19        
20        for (int i = n - 1; i >= 0; i--) {
21            while (!s2.empty() && arr[s2.top()] >= arr[i]) s2.pop();
22            right[i] = (s2.empty()) ? (n - i) : (s2.top() - i);
23            s2.push(i);
24        }
25        
26        ll result = 0;
27        for (int i = 0; i < n; i++) {
28            result = (result + (ll)arr[i] * left[i] * right[i]) % MOD;
29        }
30        return (int)result;
31    }
32};

1using System;
using System.Collections.Generic;

public class Solution {
    public int SumSubarrayMins(int[] arr) {
        int MOD = (int)1e9 + 7;
        int n = arr.Length;
        int[] dp = new int[n];
        Stack<int> stack = new Stack<int>();
        long result = 0;

        for (int i = 0; i < n; i++) {
            while (stack.Count > 0 && arr[stack.Peek()] >= arr[i]) stack.Pop();
            int k = (stack.Count > 0) ? i - stack.Peek() : i + 1;
            dp[i] = (arr[i] * k + (stack.Count > 0 ? dp[stack.Peek()] : 0)) % MOD;
            result = (result + dp[i]) % MOD;
            stack.Push(i);
        }
        return (int)result;
    }
}