<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 maximumSumOfHeights(self, heights: List[int]) -> int:
        n = len(heights)
        left  = [0 for _ in range(n)]
        right = [0 for _ in range(n)]

        q = deque()
        q.append([heights[0] , 1])
        rs = q[-1][0]
        for i in range(1 , n):
            if heights[i] >= q[-1][0]:
                left[i] = rs
                q.append([heights[i] , 1])
                rs += q[-1][0]
            else:
                removed = 0
                while len(q) and q[-1][0] > heights[i]:
                    removed += q[-1][1]
                    rs -= (q[-1][0] * q[-1][1])
                    q.pop()
                
                rs += removed * heights[i]
                left[i] = rs
                q.append([heights[i] , removed+1])
                rs += heights[i]
        
        q = deque()
        q.append([heights[n-1] , 1])
        rs = q[0][0]
        for i in range(n-2 , -1,  -1):
            if heights[i] >= q[0][0]:
                right[i] = rs
                q.appendleft([heights[i] , 1])
                rs += q[0][0]
            else:
                removed = 0
                while len(q) and q[0][0] > heights[i]:
                    removed += q[0][1]
                    rs -= (q[0][0] * q[0][1])
                    q.popleft()
                
                rs += removed * heights[i]
                right[i] = rs
                q.appendleft([heights[i] , removed+1])
                rs += heights[i]
        
        ans = 0
        for i in range(n):
            ans = max(ans , heights[i] + left[i] + right[i])
        return ans



        
99