<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, arr: List[int]) -> int:
        # mono stack + presum + presum of presum
        n = len(arr)
        
        # mono stack from left, left[i] := the index of number smaller than arr[i]
        left = [-1] * n
        right = [n] * n
        st = []
        for i, v in enumerate(arr):
            while st and arr[st[-1]] >= v:
                # st.pop() merge into one pass
                right[st.pop()] = i
            if st:
                left[i] = st[-1]
            st.append(i)
        # # mono stack from right, left[i] := the index of number smaller or equal to arr[i]
        # right = [n] * n
        # st = []
        # for i in range(n-1, -1, -1):
        #     while st and arr[st[-1]] > arr[i]: # remove = to avoid duplication 
        #         st.pop()
        #     if st:
        #         right[i] = st[-1]
        #     st.append(i)    
        
        # presum use bulit-in
        s  = list(accumulate(arr, initial = 0))
        ss = list(accumulate(s,   initial = 0))
        
        ans = 0
        for i, v in enumerate(arr):
            L, R = left[i]+1, right[i]-1
            tot = (i-L+1) * (ss[R+2] - ss[i+1]) - (R-i+1) * (ss[i+1] - ss[L])
            ans += v * tot
        return ans % (10**9+7)
        
        
    def totalStrength2(self, arr: List[int]) -> int:
        
        MOD = 10**9+7
        prefixSums = []
        positionElementProdSums = []
        positionElementProdSumsReverse = []
        runningSum = 0
        posElementProdSum = 0
        n = len(arr)
        for i in range(n):
            runningSum += arr[i]
            posElementProdSum += (i+1) * arr[i]
            prefixSums.append(runningSum)
            positionElementProdSums.append(posElementProdSum)
        posElementProdSum = 0
        for i in range(n-1,-1,-1):
            posElementProdSum += (n-i) * arr[i]
            positionElementProdSumsReverse.append(posElementProdSum)

        sum = lambda sums, l, r: sums[r] - (sums[l-1] if l-1>=0 else 0) if l <= r else 0
        totalScore = 0
        stack = []
        for i in range(n):
            while stack and arr[stack[-1][0]] > arr[i]:
                minElementIndex, leftIndex = stack.pop()
                rightIndex = i
                rightCount = rightIndex - minElementIndex
                leftCount = minElementIndex - leftIndex
                minElement = arr[minElementIndex]
                shiftedPosEleProdSum = sum(positionElementProdSums, leftIndex + 1, minElementIndex) - sum(prefixSums, leftIndex  + 1, minElementIndex) * (leftIndex  + 1)
                currRangeScore = rightCount * minElement * shiftedPosEleProdSum
                totalScore += currRangeScore
                shiftedPosEleProdSum = sum(positionElementProdSumsReverse, n-rightIndex, n-minElementIndex-2) - sum(prefixSums, minElementIndex+1, rightIndex-1)*(n-rightIndex)
                currRangeScore = leftCount * minElement * shiftedPosEleProdSum
                totalScore += currRangeScore
            if not stack: stack.append((i, -1))
            else: stack.append((i, stack[-1][0]))
        while stack:
            minElementIndex, leftIndex = stack.pop()
            rightIndex = n
            rightCount = rightIndex - minElementIndex
            leftCount = minElementIndex - leftIndex
            minElement = arr[minElementIndex]
            shiftedPosEleProdSum = sum(positionElementProdSums, leftIndex + 1, minElementIndex) - sum(prefixSums, leftIndex  + 1, minElementIndex) * (leftIndex  + 1)
            currRangeScore = rightCount * minElement * shiftedPosEleProdSum
            totalScore += currRangeScore
            shiftedPosEleProdSum = sum(positionElementProdSumsReverse, n-rightIndex, n-minElementIndex-2) - sum(prefixSums, minElementIndex+1, rightIndex-1)*(n-rightIndex)
            currRangeScore = leftCount * minElement * shiftedPosEleProdSum
            totalScore += currRangeScore
        return totalScore % MOD


856