1
impl Solution {
2
  pub fn total_strength(strength: Vec<i32>) -> i32 {
3
    const MOD: i64 = 1_000_000_007;
4
    let strength = strength.into_iter().map(|x| x as i64).collect::<Vec<_>>();
5
    let N = strength.len();
6
    let N_i64 = strength.len() as i64;
7

8
    let mut ps_l = vec![0; strength.len() + 1];
9
    let mut pm_l = vec![0; strength.len() + 1];
10

11
    for i in 0..N {
12
      ps_l[i + 1] = (ps_l[i] + strength[i]) % MOD;
13
      let i_64 = i as i64;
14
      pm_l[i + 1] = (pm_l[i] + (i_64 + 1) * strength[i]) % MOD;
15
    }
16

17
    let mut ps_r = vec![0; strength.len() + 1];
18
    let mut pm_r = vec![0; strength.len() + 1];
19

20
    for i in (0..N).rev() {
21
      ps_r[i] = (ps_r[i + 1] + strength[i]) % MOD;
22
      let i_64 = i as i64;
23
      pm_r[i] = (pm_r[i + 1] + (N_i64 - i_64) * strength[i]) % MOD;
24
    }
25

26
    let mut stack = vec![];
27
    let mut ans = 0_i64;
28

29
    for right in 0..=N {
30
      while !stack.is_empty() && (right == N || strength[*stack.last().unwrap()] >= strength[right])
31
      {
32
        let pivot = stack.pop().unwrap();
33
        let pivot_i64 = pivot as i64;
34

35
        let left_i64 = stack.last().map(|x| *x as i64 + 1).unwrap_or(0);
36
        let left = left_i64 as usize;
37

38
        let right_i64 = right as i64;
39

40
        let left_sum =
41
          (MOD + pm_l[pivot + 1] - pm_l[left] - left_i64 * (ps_l[pivot + 1] - ps_l[left]) % MOD)
42
            % MOD;
43

44
        let right_sum = (MOD + pm_r[pivot + 1]
45
          - pm_r[right]
46
          - (N_i64 - right_i64) * (ps_r[pivot + 1] - ps_r[right]))
47
          % MOD;
48

49
        let all_sum =
50
          (left_sum * (right_i64 - pivot_i64) + right_sum * (pivot_i64 - left_i64 + 1)) % MOD;
51

52
        ans = (ans + all_sum * strength[pivot]) % MOD;
53
      }
54
      stack.push(right);
55
    }
56
    ans as i32
57
  }
58
}