<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, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        left = [0]
        right = [0]
        stack = [(maxHeights[0], 0)]
        for i in range(1,len(maxHeights)):
            while len(stack) and stack[-1][0] >= maxHeights[i]:
                stack.pop(-1)
            if len(stack) == 0:
                left.append(maxHeights[i] * i)
            else:
                left.append(
                    maxHeights[i] * (i - stack[-1][1] - 1) \
                    + left[stack[-1][1]] \
                    + stack[-1][0]
                )
            stack.append((maxHeights[i], i))

        stack = [(maxHeights[-1], n-1)]
        for i in range(len(maxHeights)-2, -1, -1):
            while len(stack) and stack[-1][0] >= maxHeights[i]:
                stack.pop(-1)
            if len(stack) == 0:
                right.append(maxHeights[i] * ((n-1)-i))
            else:
                right.append(
                    maxHeights[i] * (stack[-1][1] - i - 1) \
                    + right[(n-1) - stack[-1][1]] \
                    + stack[-1][0]
                )
            stack.append((maxHeights[i], i))
        right = right[::-1]
        ret = -1
        for i in range(n):
            ret = max(ret, left[i] + maxHeights[i] + right[i])
        return ret

# Questions
# 1. can we repeat the heights?
# 2. maximum value of n?
# 3. can the height be 0?


# 1. Naive Solution
# iterate max Heights
# cur_height = min(maxHeights[i], prev_height)
# prev_height = cur_height
# height += cur_height
# for all i -> O(n ^ 2)


# choose i as the peak, j < i < k
# heights[j] = min( heights[j+1], max_heights[j] )
# heights[k] = min( heights[k+1], max_heights[k] )


# if i is the peak: heights[i] = heights[i]
# if i == j: heights[i] = lowest(heights[i:n]) -> maximum value it can achieve (left)
# if i == k: heights[i] = lowest(heights[:i]) -> maximum value it can achieve (right)


# dp => [peak, left, right]
# dp[i][0] = dp[i-1][1] + max_heights[i]
# dp[i][1] = dp[i-1][1] + heights_left[i]
# dp[i][2] = max(dp[i-1][0] + heights_right[i], dp[i-1][2] + heights_right[i])


# O(n)


# Variables
# 1. DP 
#     O(n)
#     edge cases? :
#         empty
#         one variable
#         too many
# 2. heights_right / heights_left
#     O(n)
#     edge cases?
#         empty
#         one variable
#         too many


# maxHeights = [5,3,4,1,1]
# heights_left = [1, 1, 1, 1, 1]
# heights_right = [5, 3, 3, 1, 1]


709