<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 {
public:
    long long countSubarrays(vector<int>& nums, int k) {
        int maxVal = *std::max_element(nums.begin(), nums.end());
        int len = nums.size();
        vector<long long> prefix(len);
        prefix[0] = nums[0] == maxVal;
        for (int i = 1; i < len; i++) {
            prefix[i] = prefix[i-1] + (nums[i] == maxVal);
        }

        long long totalCount = 0;
        int left = -1, right = 0;
        while (right < len && left < right) {
            int leftCount = left == -1 ? 0 : prefix[left];
            int rightCount = prefix[right];
            if (rightCount-leftCount >= k) {
                totalCount += len-right;
                left ++;
                if (left == right && right < len) {
                    right ++;
                }
            } else {
                right ++;
            }
        }

        return totalCount;
    }
};
130100