<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:
#         mx = max(nums)

#         beg = 0
#         end = k
#         total = 0

#         dic = {str([1,2,3])[1:-1] : 3}

#         print(dic)

#         c = -1
#         while beg != len(nums) - k + 1:# 0 1 2 3 4:
#             while end < len(nums) + 1:
#                 arr = nums[beg:end] 
#                 print(arr)
#                 print(f"beg = {beg} , end = {end}")
#                 if str(arr)[1:-1] in dic.keys():
#                     total += len(nums) - k
#                     break
#                 else:
#                     l = arr.count(mx)
#                     if l >= k:
#                         dic[str(nums[beg:end])[1:-1]] = l
#                         total += 1

#                     end += 1
                
#             c += 1
#             beg += 1
#             if end < len(nums) - 1:
#                 end = beg + c + k
#             else:
#                 end = len(nums) - 1
#             print(f"end = {end}")
#             print(f"c = {c}")
#             print(f"bg = {beg}")


#         print(dic)


#         # l = len(nums)
#         # for beg in range(l):
#         #     for end in range(l):
#         #         if nums[beg:end + 1].count(mx) >= k:
#         #             total += 1


#         return total


#         def div_conc(self, ls):
#             return ls

class Solution:
    def countSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        freq = defaultdict(int)
        maxi = max(nums)
        i = j = 0
        ans = 0
        while j < n:
            freq[nums[j]] += 1
            while freq.get(maxi, 0) >= k:
                ans += n - j
                freq[nums[i]] -= 1
                i += 1
            j += 1
        return ans

        

            




        

990