1
class Solution {
2
  public int totalStrength(int[] strength) {
3
    int mod = 1000000007;
4

5
    int len = strength.length;
6

7
    long[] prefix = prefixSum(strength, len, mod);
8

9
    Deque<Integer> stack = new ArrayDeque<>();
10
    stack.push(-1);
11

12
    long ans = 0;
13
    for (int i = 0; i < len; i++) {
14
      while (stack.peek() != -1 && strength[i] <= strength[stack.peek()]) {
15
        int mid = stack.pop();
16
        int left = stack.peek() + 1;
17
        int right = i - 1;
18

19
        int n = (mid - left);
20
        int t = (right - mid);
21

22
        long val = (1l * (1 + n) * (prefix[right + 2] - prefix[mid + 1]) + mod) % mod;
23
        val -= (1l * (1 + t) * (prefix[mid + 1] - prefix[left]) + mod) % mod;
24
        val *= strength[mid];
25

26
        ans += val;
27
        ans %= mod;
28
      }
29

30
      stack.push(i);
31
    }
32

33
    int right = len - 1;
34
    while (stack.peek() != -1) {
35
      int mid = stack.pop();
36
      int left = stack.peek() + 1;
37

38
      int n = (mid - left);
39
      int t = (right - mid);
40

41
      long val = (1l * (1 + n) * (prefix[right + 2] - prefix[mid + 1]) + mod) % mod;
42
      val -= (1l * (1 + t) * (prefix[mid + 1] - prefix[left]) + mod) % mod;
43
      val *= strength[mid];
44

45
      ans += val;
46
      ans %= mod;
47
    }
48

49
    return (int) ((ans + mod) % mod);
50
  }
51

52
  private long[] prefixSum(int[] strength, int len, int mod) {
53
    long[] prefix = new long[len + 1];
54

55
    for (int i = 0; i < len; i++) {
56
      prefix[i + 1] = prefix[i] + strength[i];
57
    }
58

59
    long[] doublePrefix = new long[len + 2];
60
    for (int i = 0; i <= len; i++) {
61
      doublePrefix[i + 1] = (doublePrefix[i] + prefix[i]) % mod;
62
    }
63

64
    return doublePrefix;
65
  }
66
}