<p>You are given a <strong>0-indexed</strong> array <code>maxHeights</code> of <code>n</code> integers.</p>

<p>You are tasked with building <code>n</code> towers in the coordinate line. The <code>i<sup>th</sup></code> tower is built at coordinate <code>i</code> and has a height of <code>heights[i]</code>.</p>

<p>A configuration of towers is <strong>beautiful</strong> if the following conditions hold:</p>

<ol>
	<li><code>1 &lt;= heights[i] &lt;= maxHeights[i]</code></li>
	<li><code>heights</code> is a <strong>mountain</strong> array.</li>
</ol>

<p>Array <code>heights</code> is a <strong>mountain</strong> if there exists an index <code>i</code> such that:</p>

<ul>
	<li>For all <code>0 &lt; j &lt;= i</code>, <code>heights[j - 1] &lt;= heights[j]</code></li>
	<li>For all <code>i &lt;= k &lt; n - 1</code>, <code>heights[k + 1] &lt;= heights[k]</code></li>
</ul>

<p>Return <em>the <strong>maximum possible sum of heights</strong> of a beautiful configuration of towers</em>.</p>

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

<pre>
<strong>Input:</strong> maxHeights = [5,3,4,1,1]
<strong>Output:</strong> 13
<strong>Explanation:</strong> One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 &lt;= heights[i] &lt;= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.</pre>

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

<pre>
<strong>Input:</strong> maxHeights = [6,5,3,9,2,7]
<strong>Output:</strong> 22
<strong>Explanation:</strong> One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 &lt;= heights[i] &lt;= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.</pre>

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

<pre>
<strong>Input:</strong> maxHeights = [3,2,5,5,2,3]
<strong>Output:</strong> 18
<strong>Explanation:</strong> One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 &lt;= heights[i] &lt;= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.
</pre>

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

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

class Solution:
    def maximumSumOfHeights(self, heights: List[int]) -> int:
        '''
        6,5,3,9,2,7

        [6] 5   3   3  2  2 = 21
         5 [5]  3   3  2  2 = 20
         3  3  [3]  3  2  2 = 16
         3  3   3  [9] 2  2 = 22    <-  
         2  2.  2   2  2  2 = 12
         2  2   2   2  2  7 = 17  
        
        6. 10. 9.  18. 10. 17 <- prefix_sum_left
        21.15. 10.  13. 4. 7. <- prefix_sum_right
        21 20. 16   22. 12 17 -> 21
        prefix_sum_left[i] + prefix_sum_right[i] - heights[i]


        0.  1. 2.  3.   4  5
        6.  5. 3.  9.   2. 7
        6. 10. 9.  18. 10. 17

        6  10  9   18. 10 17
        
               i.      st[-1]
        0.  1. 2.  3.   4  5
        6.  5. 3.  9.   2. 7
        21  15   10  13    4  7
        [4,2]

        0,1,2,3,4,5 
        6,5,3,9,2,7

        1,2,4,4,6,6

        -1,-1,-1,2,-1,4   
        
        '''
        n = len(heights)
        prefix_sum_left = self.cal_prefix_sum_left(heights, n)
        # print(prefix_sum_left)
        prefix_sum_right = self.cal_prefix_sum_right(heights,n)
        # print(prefix_sum_right)
        ans = -1
        for i in range(n):
            ans = max(ans,prefix_sum_left[i] + prefix_sum_right[i] - heights[i])

        return ans

    def cal_prefix_sum_left(self, heights, n):
        arr = [0] * n
        st = []
        for i in range(n):
            h = heights[i]
            while st and heights[st[-1]] >= h:
                st.pop()
            if not st:
                arr[i] = h * (i+1)
            else:
                arr[i] = arr[st[-1]] + h * (i - st[-1])
            st.append(i)
        return arr
    
    def cal_prefix_sum_right(self, heights, n):
        arr = [0] * n
        st = []
        for i in range(n-1,-1,-1):
            h = heights[i]
            while st and heights[st[-1]] >= h:
                st.pop()

            if not st:
                arr[i] = h * (n-i)
            else:
                arr[i] = arr[st[-1]] + h * (st[-1] - i)
            st.append(i)
        return arr




466