<p>You are given a <strong>0-indexed</strong> integer array <code>nums</code>. For each index <code>i</code> (<code>1 &lt;= i &lt;= nums.length - 2</code>) the <strong>beauty</strong> of <code>nums[i]</code> equals:</p>

<ul>
	<li><code>2</code>, if <code>nums[j] &lt; nums[i] &lt; nums[k]</code>, for <strong>all</strong> <code>0 &lt;= j &lt; i</code> and for <strong>all</strong> <code>i &lt; k &lt;= nums.length - 1</code>.</li>
	<li><code>1</code>, if <code>nums[i - 1] &lt; nums[i] &lt; nums[i + 1]</code>, and the previous condition is not satisfied.</li>
	<li><code>0</code>, if none of the previous conditions holds.</li>
</ul>

<p>Return<em> the <strong>sum of beauty</strong> of all </em><code>nums[i]</code><em> where </em><code>1 &lt;= i &lt;= nums.length - 2</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> For each index i in the range 1 &lt;= i &lt;= 1:
- The beauty of nums[1] equals 2.
</pre>

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

<pre>
<strong>Input:</strong> nums = [2,4,6,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong> For each index i in the range 1 &lt;= i &lt;= 2:
- The beauty of nums[1] equals 1.
- The beauty of nums[2] equals 0.
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,2,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> For each index i in the range 1 &lt;= i &lt;= 1:
- The beauty of nums[1] equals 0.
</pre>

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

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def sumOfBeauties(self, nums: List[int]) -> int:
        # Create an integer variable, n, representing the length of nums, used for easy reference. Create an integer variable, result, which will be updated to equal the sum of beauty of all nums[i] where 1 <= i <= n - 2, initialized to 0. Create an integer variable, prefix_max, that keeps track of the maximum value in the range [0, i - 1], initialized to nums[0]. Create an array, suffix_mins, where suffix_mins[i] records the minimum value in the range [i + 1, n - 1], initialized with infinity as its only element.
        n = len(nums)
        result = 0
        prefix_max = nums[0]
        suffix_mins = [float('inf')]
        # Iterate backwards over the range [n - 1, 2] using i. Create a variable, curr_min, initialized to the minimum of nums[i] and suffix_mins[-1]. Then, append curr_min to suffix_mins.
        for i in range(n - 1, 1, -1):
            curr_min = min(nums[i], suffix_mins[-1])
            suffix_mins.append(curr_min)
        # Iterate over the range [1, n - 2] using i. Pop the last element from suffix_mins as suffix_min. If prefix_max < nums[i] < suffix_min, increment result by 2. Otherwise if nums[i - 1] < nums[i] < nums[i + 1], increment result by 1. Then, update prefix_max by setting it equal to the maximum of prefix_max and nums[i].
        for i in range(1, n - 1):
            suffix_min = suffix_mins.pop()
            if prefix_max < nums[i] < suffix_min:
                result += 2
            elif nums[i - 1] < nums[i] < nums[i + 1]:
                result += 1
            prefix_max = max(prefix_max, nums[i])
        # After exiting the for loop, return result.
        return result
31800