<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:
        maxcount = 0
        stack = deque()
        stack.append(0) #contains indices of ascensding order elements 
        preval = [-1]*len(maxHeights) #contains values of last smaller element, -1 means they are the smallest
        for i in range(1,len(maxHeights)) :
            if maxHeights[i] > maxHeights[stack[-1]] :
                stack.append(i)
                preval[i] = i-1
            else :
                while stack and maxHeights[i] <= maxHeights[stack[-1]] :
                    preval[i] = preval[stack[-1]]
                    stack.pop()
                stack.append(i) 
        postval = [-1]*len(maxHeights) #contains values of last smaller element, -1 means they are the smallest
        while stack :
            stack.pop()
        stack.append(len(maxHeights) - 1)
        for i in range(len(maxHeights) - 2,-1,-1) :
            if maxHeights[i] > maxHeights[stack[-1]] :
                stack.append(i)
                postval[i] = i+1
            else :
                while stack and maxHeights[i] <= maxHeights[stack[-1]] :
                    postval[i] = postval[stack[-1]]
                    stack.pop()
                stack.append(i) 
        # print("preval:postval")
        # print(maxHeights)
        # print(preval)
        # print(postval)
        prevalues = [0]*len(maxHeights)
        for i in range(1,len(maxHeights)) :
            if preval[i] == -1 :
                prevalues[i] = i*maxHeights[i]
            else :
                prevalues[i] = (i-preval[i]-1)*maxHeights[i] + (prevalues[preval[i]] + maxHeights[preval[i]])
        
        postvalues = [0]*len(maxHeights)
        for i in range(len(maxHeights)-2,-1,-1) :
            if postval[i] == -1 :
                postvalues[i] = (len(maxHeights)-i-1)*maxHeights[i]
            else :
                postvalues[i] = postvalues[postval[i]] + (postval[i] - i -1)*maxHeights[i] + maxHeights[postval[i]]
        # print("prevalues")
        # print(prevalues)
        # print("postvalues")
        # print(postvalues)
        for i in range(len(maxHeights)) :
            if prevalues[i] + postvalues[i] + maxHeights[i] > maxcount :
                maxcount = prevalues[i] + postvalues[i] + maxHeights[i]


        return maxcount
41100