<p>You are given an array <code>heights</code> of <code>n</code> integers representing the number of bricks in <code>n</code> consecutive towers. Your task is to remove some bricks to form a <strong>mountain-shaped</strong> tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing.</p>

<p>Return the <strong>maximum possible sum</strong> of heights of a mountain-shaped tower arrangement.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">heights = [5,3,4,1,1]</span></p>

<p><strong>Output:</strong> <span class="example-io">13</span></p>

<p><strong>Explanation:</strong></p>

<p>We remove some bricks to make <code>heights =&nbsp;[5,3,3,1,1]</code>, the peak is at index 0.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">heights = [6,5,3,9,2,7]</span></p>

<p><strong>Output:</strong> <span class="example-io">22</span></p>

<p><strong>Explanation:</strong></p>

<p>We remove some bricks to make <code>heights =&nbsp;[3,3,3,9,2,2]</code>, the peak is at index 3.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">heights = [3,2,5,5,2,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">18</span></p>

<p><strong>Explanation:</strong></p>

<p>We remove some bricks to make <code>heights = [2,2,5,5,2,2]</code>, the peak is at index 2 or 3.</p>
</div>

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

<ul>
	<li><code>1 &lt;= n == heights.length &lt;= 10<sup>3</sup></code></li>
	<li><code>1 &lt;= heights[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 maximumSumOfHeights(self, heights: List[int]) -> int:
        lowerDistanceLeft = self.distanceFromLower(heights)

        prefixSum = self.prefixSum(heights)
        heightsSum = sum(heights)
        
        leftRemovals = [0 for _ in heights]
        for i in range(len(heights)):
            toRemove = 0
            
            #stack = [heights[i]]

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

                #for j in range(i - 1, -1, -1):
                #    if heights[j] <= heights[i]:
                #        toRemove += leftRemovals[j]
                #        break
                #    else:
                #        toRemove += heights[j] - heights[i]
            
            leftRemovals[i] = toRemove
        
        rightRemovals = [0 for _ in heights]
        for i in range(len(heights) - 1, -1, -1):
            toRemove = 0

            for j in range(i + 1, len(heights)):
                if heights[j] <= heights[i]:
                    toRemove += rightRemovals[j]
                    break
                else:
                    toRemove += heights[j] - heights[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


206