1
class Solution:
2
    def totalStrength(self, stp: List[int]) -> int:
3
        st = []
4
        n = len(stp)
5
        m1 = defaultdict(lambda: -1)
6
        ps = [0]
7
        for i in range(n):
8
            while st and stp[st[-1]] >= stp[i]:
9
                st.pop()
10
            if st:
11
                m1[i] = st[-1]
12
            st.append(i)
13
            ps.append(ps[-1] + stp[i])
14
        pss = [0]
15
        for i in ps:
16
            pss.append(pss[-1] + i)
17
        st = []
18
        m2 = defaultdict(lambda: n)
19
        for i in range(n - 1, -1, -1):
20
            while st and stp[st[-1]] > stp[i]:
21
                st.pop()
22
            if st:
23
                m2[i] = st[-1]
24
            st.append(i)
25

26
        ans = 0
27
        mod = 10**9 + 7
28
        for i in range(n):
29
            left = m1[i] + 1
30
            right = m2[i]
31
            p1 = (i + 1 - left) * (pss[right + 1] - pss[i + 1])
32
            p2 = (right - i) * (pss[i + 1] - pss[left])
33
            ans = (ans + stp[i] * (p1 - p2)) % mod
34
        return ans