<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 prefixSum(self, arr: List[int]) -> List[int]:
        cur = 0
        
        answer = [0 for _ in arr]
        for i in range(len(arr)):
            cur += arr[i]
            answer[i] = cur
        
        return answer

    # MODIFIED FROM https://www.geeksforgeeks.org/distance-from-next-greater-element/
    def distanceFromLower(self, arr: List[int]) -> int:
        # answer[i] = i - j for the greatest j such that 0 <= j < i and heights[j] <= heights[i]
            # NOTICE: could be equal to, not neccessarily lower
            # if no such j, then answer[i] = 0
        #arr = arr[::-1]

        N = len(arr)
        if N <= 1:
            return [0]
        
        # Stores the required distances
        ans = [0 for i in range(N)]
        st = [N - 1]
        
        # Maintain a stack of elements
        # in non-decreasing order
        for i in range(N - 2, -1, -1):  
            
            # If the current element exceeds 
            # the element at the top of the stack
            while(st and arr[i] < arr[st[-1]]):  
                pos = st.pop()
                ans[pos] = pos - i
                
            # Push the current index to the stack
            st.append(i)
    
        #ans.reverse()
        return ans

    def maximumSumOfHeightsI(self, heights: List[int]) -> int:
        prefixSum = self.prefixSum(heights)
        heightsSum = sum(heights)
        
        lowerDistanceLeft = self.distanceFromLower(heights)
        leftRemovals = [0 for _ in heights]
        for i in range(len(heights)):
            toRemove = 0

            if lowerDistanceLeft[i] == 0:
                toRemove = (prefixSum[i] - heights[i]) - (i * heights[i])
            else:
                temp = prefixSum[i-1] - prefixSum[i-lowerDistanceLeft[i]] - ((lowerDistanceLeft[i] - 1) * heights[i])
                toRemove = temp + leftRemovals[i-lowerDistanceLeft[i]]
            
            leftRemovals[i] = toRemove
        
        lowerDistanceLeft = None

        lowerDistanceRight = self.distanceFromLower(heights[::-1])[::-1]
        rightRemovals = [0 for _ in heights]
        for i in range(len(heights) - 1, -1, -1):
            toRemove = 0

            if lowerDistanceRight[i] == 0:
                toRemove = (prefixSum[-1] - prefixSum[i]) - ((len(heights) - (i + 1)) * heights[i])
            else:
                temp = prefixSum[i + lowerDistanceRight[i] - 1] - prefixSum[i] - ((lowerDistanceRight[i] - 1) * heights[i])
                toRemove = temp + rightRemovals[i+lowerDistanceRight[i]]
                
            rightRemovals[i] = toRemove
        
        minRemovals = min([leftRemovals[i] + rightRemovals[i] for i in range(len(heights))])

        # idea
            #definition: leftwards peak: element and everything left are non-decreasing
            #definition: rightwards peak: element and everything right are non-increasing
            # array that keeps track of removals in left and

        return heightsSum - minRemovals

    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        return self.maximumSumOfHeightsI(maxHeights)
726