<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) {
        // long long l = 0;
        // long long r = 0;
        // long long n =nums.size();
        // long long count = 0;
        // long long res = 0;
        // long long max_ele = *max_element(nums.begin(), nums.end());
        // long long flag = 1;
        // while(r<nums.size()){
        //     if(nums[r] == max_ele) count++;

        //     while(count>=k) {
        //         res+= n-r;
        //         if(nums[l] == max_ele) count--;
        //         l++;     
        //     }
        //     r++;
            
        // }

        // return res;

        std::vector<long long> indices;
    long long n = nums.size();
    long long res = 0;
    long long max_ele = *std::max_element(nums.begin(), nums.end());

    // Find all indices where the element is equal to the max element
    for (long long i = 0; i < n; i++) {
        if (nums[i] == max_ele) {
            indices.push_back(i);
        }
    }

    // If there are fewer max elements than k, return 0 as it's not possible to have a subarray of length k with max element
    if (indices.size() < k) {
        return 0;
    }

    // Calculate result based on indices of max elements
    for (long long i = 0; i <= indices.size() - k; i++) {
        // If we are considering a subarray of size k, ensure that we're within bounds
        long long end = (i + k < indices.size()) ? indices[i + k] - 1 : n - 1;

        // Adding the count of subarrays
        res += (indices[i] + 1) * (end - indices[i + k - 1] + 1);
    }

    return res;
    }
};
127600