1
class Solution {
2
  public int sumSubarrayMins(int[] arr) {
3
    int n = arr.length;
4
    int ans1[] = nsl(arr);
5
    int ans2[] = nsr(arr);
6
    long sum = 0;
7
    for (int i = 0; i < n; i++) {
8
      sum =
9
          (sum + (long) (arr[i] * (long) (ans1[i] * ans2[i]) % 1000000007) % 1000000007)
10
              % 1000000007;
11
    }
12
    return (int) sum;
13
  }
14

15
  public static int[] nsl(int arr[]) {
16
    Stack<Integer> s = new Stack<>();
17
    int ans[] = new int[arr.length];
18
    for (int i = 0; i < arr.length; i++) {
19
      while (!s.isEmpty() && arr[i] < arr[s.peek()]) {
20
        s.pop();
21
      }
22
      if (s.isEmpty()) {
23
        ans[i] = i - (-1);
24
        s.push(i);
25
      } else {
26
        ans[i] = i - s.peek();
27
        s.push(i);
28
      }
29
    }
30
    return ans;
31
  }
32

33
  public static int[] nsr(int arr[]) {
34
    Stack<Integer> s = new Stack<>();
35
    int ans[] = new int[arr.length];
36
    for (int i = arr.length - 1; i >= 0; i--) {
37
      while (!s.isEmpty() && arr[s.peek()] >= arr[i]) {
38
        s.pop();
39
      }
40
      if (s.isEmpty()) {
41
        ans[i] = arr.length - i;
42
        s.push(i);
43
      } else {
44
        ans[i] = s.peek() - i;
45
        s.push(i);
46
      }
47
    }
48
    return ans;
49
  }
50
}