<p>You are given an array of integers <code>nums</code> <strong>(0-indexed)</strong> and an integer <code>k</code>.</p>

<p>The <strong>score</strong> of a subarray <code>(i, j)</code> is defined as <code>min(nums[i], nums[i+1], ..., nums[j]) * (j - i + 1)</code>. A <strong>good</strong> subarray is a subarray where <code>i &lt;= k &lt;= j</code>.</p>

<p>Return <em>the maximum possible <strong>score</strong> of a <strong>good</strong> subarray.</em></p>

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

<pre>
<strong>Input:</strong> nums = [1,4,3,7,4,5], k = 3
<strong>Output:</strong> 15
<strong>Explanation:</strong> The optimal subarray is (1, 5) with a score of min(4,3,7,4,5) * (5-1+1) = 3 * 5 = 15. 
</pre>

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

<pre>
<strong>Input:</strong> nums = [5,5,4,5,4,1,1,1], k = 0
<strong>Output:</strong> 20
<strong>Explanation:</strong> The optimal subarray is (0, 4) with a score of min(5,5,4,5,4) * (4-0+1) = 4 * 5 = 20.
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= k &lt; nums.length</code></li>
</ul>

class Solution:
    def maximumScore(self, nums: List[int], k: int) -> int:
        '''
        
        score = min(nums[i],...,nums[j]) * (j - i + 1)

        left and right 

        left find the nearest number smaller then cur on the left

        right find the nearest number smaller then cur on the right

        from left to right 

        update the val
        '''

        n = len(nums)

        left = [0] * n

        right = [0] * n

        stack = []

        for i in range(n):

            while stack and nums[i] <= nums[stack[-1]]:

                stack.pop()

            if not stack:

                left[i] = -1

            else:

                left[i] = stack[-1]

            stack.append(i)

        stack = []

        for i in range(n-1, -1, -1):

            while stack and nums[i] <= nums[stack[-1]]:

                stack.pop()

            if not stack:

                right[i] = n

            else:

                right[i] = stack[-1]

            stack.append(i)

        res = 0

        for i in range(n):

            if left[i] + 1 <= k and k <= right[i] - 1:

                score = nums[i] * (right[i] - left[i] - 1)

                res = max(res, score)

        return res

989