<p>As the ruler of a kingdom, you have an army of wizards at your command.</p>

<p>You are given a <strong>0-indexed</strong> integer array <code>strength</code>, where <code>strength[i]</code> denotes the strength of the <code>i<sup>th</sup></code> wizard. For a <strong>contiguous</strong> group of wizards (i.e. the wizards&#39; strengths form a <strong>subarray</strong> of <code>strength</code>), the <strong>total strength</strong> is defined as the <strong>product</strong> of the following two values:</p>

<ul>
	<li>The strength of the <strong>weakest</strong> wizard in the group.</li>
	<li>The <strong>total</strong> of all the individual strengths of the wizards in the group.</li>
</ul>

<p>Return <em>the <strong>sum</strong> of the total strengths of <strong>all</strong> contiguous groups of wizards</em>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>A <strong>subarray</strong> is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> strength = [1,3,1,2]
<strong>Output:</strong> 44
<strong>Explanation:</strong> The following are all the contiguous groups of wizards:
- [1] from [<u><strong>1</strong></u>,3,1,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
- [3] from [1,<u><strong>3</strong></u>,1,2] has a total strength of min([3]) * sum([3]) = 3 * 3 = 9
- [1] from [1,3,<u><strong>1</strong></u>,2] has a total strength of min([1]) * sum([1]) = 1 * 1 = 1
- [2] from [1,3,1,<u><strong>2</strong></u>] has a total strength of min([2]) * sum([2]) = 2 * 2 = 4
- [1,3] from [<u><strong>1,3</strong></u>,1,2] has a total strength of min([1,3]) * sum([1,3]) = 1 * 4 = 4
- [3,1] from [1,<u><strong>3,1</strong></u>,2] has a total strength of min([3,1]) * sum([3,1]) = 1 * 4 = 4
- [1,2] from [1,3,<u><strong>1,2</strong></u>] has a total strength of min([1,2]) * sum([1,2]) = 1 * 3 = 3
- [1,3,1] from [<u><strong>1,3,1</strong></u>,2] has a total strength of min([1,3,1]) * sum([1,3,1]) = 1 * 5 = 5
- [3,1,2] from [1,<u><strong>3,1,2</strong></u>] has a total strength of min([3,1,2]) * sum([3,1,2]) = 1 * 6 = 6
- [1,3,1,2] from [<u><strong>1,3,1,2</strong></u>] has a total strength of min([1,3,1,2]) * sum([1,3,1,2]) = 1 * 7 = 7
The sum of all the total strengths is 1 + 9 + 1 + 4 + 4 + 4 + 3 + 5 + 6 + 7 = 44.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> strength = [5,4,6]
<strong>Output:</strong> 213
<strong>Explanation:</strong> The following are all the contiguous groups of wizards: 
- [5] from [<u><strong>5</strong></u>,4,6] has a total strength of min([5]) * sum([5]) = 5 * 5 = 25
- [4] from [5,<u><strong>4</strong></u>,6] has a total strength of min([4]) * sum([4]) = 4 * 4 = 16
- [6] from [5,4,<u><strong>6</strong></u>] has a total strength of min([6]) * sum([6]) = 6 * 6 = 36
- [5,4] from [<u><strong>5,4</strong></u>,6] has a total strength of min([5,4]) * sum([5,4]) = 4 * 9 = 36
- [4,6] from [5,<u><strong>4,6</strong></u>] has a total strength of min([4,6]) * sum([4,6]) = 4 * 10 = 40
- [5,4,6] from [<u><strong>5,4,6</strong></u>] has a total strength of min([5,4,6]) * sum([5,4,6]) = 4 * 15 = 60
The sum of all the total strengths is 25 + 16 + 36 + 36 + 40 + 60 = 213.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= strength.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= strength[i] &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def totalStrength(self, strength: List[int]) -> int:
        mod = 10 ** 9 + 7

        a = [0] + strength + [0]

        ps = [0] * len(a)
        ms = [0] * len(a)
        for i in range(1, len(a)):
            ps[i] = (ps[i - 1] + a[i])
            ms[i] = (ms[i - 1] + a[i] * i)

        rps = [0] * len(a)
        rms = [0] * len(a)
        for i in range(len(a) - 2, -1, -1):
            rps[i] = (rps[i + 1] + a[i])
            rms[i] = (rms[i + 1] + a[i] * (len(a) - i - 1))

        # for i in [a, ps, ms, rps, rms]:
        #     print(i)
        # print('-' * 30)

        def fact(idx, l, r):
            assert(l > 0 and r > 0)
            x = ms[idx] - ms[idx - l] - (ps[idx] - ps[idx - l]) * (idx - l)
            y = rms[idx] - rms[idx + r] - (rps[idx] - rps[idx + r]) * (len(a) - 1 - idx - r)
            assert(x > 0 and y >= 0)
            return x, y
        
        ret = 0
        q = [0]
        for i in range(1, len(a)):
            while q and a[i] < a[q[-1]]:
                l, c, r = q[-2], q[-1], i
                dl, dr = c - l, r - c
                f1, f2 = fact(c, dl, dr)
                f3 = f1 * dr + f2 * dl - a[c] * dl * dr
                t = f3 * a[c] % mod
                ret = (ret + t) % mod
                q.pop()
            q.append(i)

        return ret

        # Solution 2
        # def f(a):
        #     ps = [a[0][0]]
        #     ms = [a[0][0]]
        #     for i in range(1, len(a)):
        #         ps.append((ps[-1] + a[i][0]) % mod)
        #         ms.append((ms[-1] + a[i][0] * i % mod) % mod)

        #     retx = rety = 0
        #     q = [(0,0,0,1)]  # idx, left, pivot, len
        #     for i in range(1, len(a)):
        #         while q and a[q[-1][0]] > a[i]:
        #             r = i - q[-1][0]
        #             xx = q[-1][1] * r * a[q[-1][0]][0] % mod
        #             yy = q[-1][2] * r * a[q[-1][0]][0] % mod
        #             retx = (retx + xx) % mod
        #             rety = (rety + yy) % mod
        #             # print(q[-1], r, a[q[-1][0] - q[-1][3] + 1 : q[-1][0] + r], (xx, yy))
        #             q.pop()

        #         d = i - q[-1][0]
        #         t = ((ms[i] - ms[i - d] + mod) % mod - (ps[i] - ps[i - d] + mod) % mod * (i - d) % mod + mod) % mod
        #         p = a[i][0] * d % mod
        #         l = (t - p + mod) % mod
        #         q.append((i, l, p, d))
        #     return retx, rety
        
        # a = list(zip(strength, range(len(strength))))
        # x = f([(0,0)] + a + [(0,0)])
        # y = f([(0,0)] + a[::-1] + [(0,0)])
        # assert(x[1] == y[1])
        # return (x[0] + x[1] + y[0]) % mod

        # My First Solution
        # ret = 0
        # a = [0] + strength
        # q = [(0, 0, 0, 0,0,0)]  # idx,f1,t2,  f2,SpanSum,span
        
        # for i in range(1, len(a)):
        #     f2,ss,span = a[i],a[i],1
        #     while a[i] < a[q[-1][0]]:
        #         f2 += ss * q[-1][5] + q[-1][3]
        #         ss += q[-1][4]
        #         span += q[-1][5]
        #         q.pop()
            
        #     span2 = i - q[-1][0]
        #     assert(span == span2)

        #     t0 = f2 * a[i] % mod
        #     t1 = q[-1][1] * ss % mod
        #     t2 = (q[-1][2] + t0 + t1) % mod
        #     ret = (ret + t2) % mod
        #     f = (q[-1][1] + span * a[i] % mod) % mod
        #     q.append((i, f, t2,f2,ss,span))
    
        # return ret
1182