1
class Solution {
2
 public:
3
  int mod = 1e9 + 7;
4
  int Value(vector<int> a, int n) {
5
    vector<long long> pre(n + 2, 0);
6
    for (int i = 1; i <= n; i++) pre[i] = (pre[i - 1] + a[i - 1]) % mod;
7
    for (int i = 1; i <= n + 1; i++) pre[i] = (pre[i - 1] + pre[i]) % mod;
8
    for (int i = n + 1; i > 0; i--) pre[i] = pre[i - 1];
9

10
    vector<int> l(n, -1), r(n, n);
11
    stack<int> st;
12
    // Find all left index
13
    for (int i = 0; i < n; i++) {
14
      while (!st.empty() && a[st.top()] >= a[i]) st.pop();
15
      if (!st.empty()) l[i] = st.top();
16

17
      st.push(i);
18
    }
19

20
    while (!st.empty()) st.pop();
21

22
    // Find all right index
23
    for (int i = n - 1; i >= 0; i--) {
24
      while (!st.empty() && a[st.top()] > a[i]) st.pop();
25

26
      if (!st.empty()) r[i] = st.top();
27

28
      st.push(i);
29
    }
30
    // for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<"\n";
31
    // for(int i=0;i<n;i++) cout<<l[i]<<" "; cout<<"\n";
32
    // for(int i=0;i<n;i++) cout<<r[i]<<" "; cout<<"\n";
33

34
    long long ans = 0;
35
    for (int i = 0; i < n; ++i) {
36
      ans += (((pre[r[i] + 1] - pre[i + 1]) * (i - l[i]) % mod + mod * 2 -
37
               (pre[i + 1] - pre[l[i] + 1]) * (r[i] - i) % mod) %
38
              mod * a[i]) %
39
             mod;
40
      ans %= mod;
41
    }
42
    return (int)ans;
43
  }
44
  int totalStrength(vector<int> &s) {
45
    int n = s.size();
46
    return Value(s, n);
47
  }
48
};