<p>You are given an integer array <code>nums</code> and a <strong>positive</strong> integer <code>k</code>.</p>

<p>Return <em>the number of subarrays where the <strong>maximum</strong> element of </em><code>nums</code><em> appears <strong>at least</strong> </em><code>k</code><em> times in that subarray.</em></p>

<p>A <strong>subarray</strong> is a contiguous sequence of elements within an array.</p>

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

<pre>
<strong>Input:</strong> nums = [1,3,2,3,3], k = 2
<strong>Output:</strong> 6
<strong>Explanation:</strong> The subarrays that contain the element 3 at least 2 times are: [1,3,2,3], [1,3,2,3,3], [3,2,3], [3,2,3,3], [2,3,3] and [3,3].
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,4,2,1], k = 3
<strong>Output:</strong> 0
<strong>Explanation:</strong> No subarray contains the element 4 at least 3 times.
</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;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= k &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        '''
        for each match (matches == k)
        1. 1
        2. left - mostLeft
        3. len(n) - 1 - right
        4. 2 * 3 (for each left side, can match with right side)
        '''
        mostLeft,l,r = 0,0,0
        mostRight = len(nums) - 1

        maxNum = max(nums)
        kFound = 0
        if nums[0] == maxNum:
            kFound = 1
        
        res = 0 
        while r < len(nums):
            # print("1",mostLeft,l,r,mostRight, kFound)
            while r + 1 < len(nums) and kFound < k: # keep expanding until find k
                r += 1
                kFound += 1 if nums[r] == maxNum else 0

            # keep moving until l reaches first/next maxNum
            while nums[l] != maxNum and l < r:
                # print(l)
                l += 1

            # print("2",mostLeft,l,r,mostRight, kFound)
            # if l < r and kFound > k: #make window smaller
            #     l += 1
            #     mostLeft = l #do this once only
            #     while l < r: #stop until find next maxNum
            #         if nums[l] == maxNum: #then stop
            #             kFound -= 1
            #             break
            # print("3",mostLeft,l,r,mostRight, kFound)

            # #guaranteed that kFound == k
            if k == kFound:
                leftNum = l - mostLeft
                rightNum = mostRight - r
                mix = rightNum * leftNum
                res += leftNum + rightNum + mix + 1
            # print("add",mostLeft,l,r,mostRight, kFound, res)
            
            # #keep expanding right again until find next k
            kFound -= 1 #because window shift right
            l += 1
            mostLeft = l
            r += 1
            kFound += 1 if r < len(nums) and nums[r] == maxNum else 0
            # while r < len(nums) and kFound <= k:
            #     if nums[r] == maxNum:
            #         kFound += 1
            # print("expand right to next k",mostLeft,l,r,mostRight, kFound)

        return res


931