<p>You are given an array of <strong>positive</strong> integers <code>nums</code>.</p>

<p>Return the number of <span data-keyword="subarray-nonempty">subarrays</span> of <code>nums</code>, where the <strong>first</strong> and the <strong>last</strong> elements of the subarray are <em>equal</em> to the <strong>largest</strong> element in the subarray.</p>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,4,3,3,2]</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:</p>

<ul>
	<li>subarray <code>[<strong><u>1</u></strong>,4,3,3,2]</code>, with its largest element 1. The first element is 1 and the last element is also 1.</li>
	<li>subarray <code>[1,<u><strong>4</strong></u>,3,3,2]</code>, with its largest element 4. The first element is 4 and the last element is also 4.</li>
	<li>subarray <code>[1,4,<u><strong>3</strong></u>,3,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[1,4,3,<u><strong>3</strong></u>,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[1,4,3,3,<u><strong>2</strong></u>]</code>, with its largest element 2. The first element is 2 and the last element is also 2.</li>
	<li>subarray <code>[1,4,<u><strong>3,3</strong></u>,2]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
</ul>

<p>Hence, we return 6.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [3,3,3]</span></p>

<p><strong>Output:</strong> <span class="example-io">6</span></p>

<p><strong>Explanation:</strong></p>

<p>There are 6 subarrays which have the first and the last elements equal to the largest element of the subarray:</p>

<ul>
	<li>subarray <code>[<u><strong>3</strong></u>,3,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,<strong><u>3</u></strong>,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,3,<u><strong>3</strong></u>]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[<strong><u>3,3</u></strong>,3]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[3,<u><strong>3,3</strong></u>]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
	<li>subarray <code>[<u><strong>3,3,3</strong></u>]</code>, with its largest element 3. The first element is 3 and the last element is also 3.</li>
</ul>

<p>Hence, we return 6.</p>
</div>

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

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1]</span></p>

<p><strong>Output:</strong> <span class="example-io">1</span></p>

<p><strong>Explanation:</strong></p>

<p>There is a single subarray of <code>nums</code> which is <code>[<strong><u>1</u></strong>]</code>, with its largest element 1. The first element is 1 and the last element is also 1.</p>

<p>Hence, we return 1.</p>
</div>

<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;= 10<sup>9</sup></code></li>
</ul>

# class Solution:
#     def numberOfSubarrays(self, nums: List[int]) -> int:
        # intuition- a pointer and a hashmap of freq. the technique resembles the algo for best time to buy and cell stock
        # approach-
        # step1 1:
        #   run on the array and count freq of each unique number, save it in a freqMap
        # step 2:
        #   init r pointer.curMax=nums[0] 
        #   while r< len of nums  
        #       if nums[r]==curMax then numOfClosers+=1 
        #       if nums[r]>curMax then{ 
        #       result+= numOfClosers*(numOfClosers-1))/2 (if we encounter an new max, we will calculate the amount of subarrays that starts and ends with previus Max by the formula (numOfClosers*(numOfClosers-1))/2 and add it to result.
        #           curmax=nums[r]
        #           numOfClosers=1 }
        
        #       freqMap[nums[r]]-=1 ( each time we increment r we will reduce the freq of nums[r] from the freqMap)
        #        if freqMap[nums[r]==0 then we can set curMax to min int value (if there are no more nums[r] ahead we know we dont need to check and we can reset curMax so the next element will be the new curmax)
        #       r++ 
        #  
        #   
        #
        #  of course we have to add to result the numbers of elements (n) because each element on its own is a valid subarray
        # I WAS VERY CLOSE! BUT NOT QUITE RIGHT- THE FOLLOWING ANSWER HAVE A SIMILAR APPROACH FOR FREQ COUNT BUT IT UTILIZE A STACK (NOT QUITE CLASSIC MONOTONIC) TO COUNT THE FREQ AND SO ON.. A GREAT SOLUTION!
from typing import List

class Solution:
    def numberOfSubarrays(self, nums: List[int]) -> int:
        st = deque()
        ans = 0
        for x in nums:
            while st and st[-1][0] < x:
                st.pop()
            if not st or st[-1][0] != x:
                st.append((x, 1))
            else:
                st[-1] = (st[-1][0], st[-1][1] + 1)
            ans += st[-1][1]
        return ans

31600