<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:
        def get_lsum(i):
            _arr = heights[:i]
            s = []
            f = []
            for i, n in enumerate(_arr):
                # print(f"{s = } | {f = } | {n = }")
                n_freqs = 1
                while s and s[-1] >= n:
                    s.pop()
                    
                    n_freqs += f.pop()

                s.append(n)
                f.append(n_freqs)
            # print(f"{s = } | {f = }")
            res = 0
            for _n, _f in zip(s, f):
                res += (_n*_f)
            return res
        def get_rsum(i):
            _arr = heights[i+1:]
            s = []
            f = []
            for n in _arr:
                if s and n >= s[-1]:
                    f[-1] += 1
                else:
                    s.append(n)
                    f.append(1)
            res = 0
            for _n, _f in zip(s, f):
                res += (_n*_f)
            return res

        mps = 0
        for idx in range(len(heights)):
            if idx > 0:
                if heights[idx] < heights[idx-1]:
                    continue
            lsum = get_lsum(idx)
            rsum = get_rsum(idx)
            
            # print(f"{idx = } | {lsum = } | {rsum = } | sum: {lsum+rsum+heights[idx]} | {mps = }")
            mps = max(mps, lsum+rsum+heights[idx])

        return mps
764