<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 n=nums.size(), i=0, mx=0, f=0;
        long long ans=0;
        vector<long long> dp(n, 0);

        for(int j=0; j<nums.size(); j++)
        {
            mx=max(mx, nums[j]);
        }
        
        for(int j=0; j<nums.size(); j++)
        {
            if(nums[j]==mx)
            {
                f++;
            }

            long long cnt=0;

            while(f>=k)
            {
                cnt++;

                if(nums[i]==mx)
                {
                    f--;
                }

                i++;
            }

            dp[j]=cnt;

            if(j-1>=0)
            {
                dp[j]+=dp[j-1];
            }

            ans+=dp[j];
        }

        return ans;
        
        /*
        int i=0, mx=0, f=0;
        long long cnt=0;

        for(int j=0; j<nums.size(); j++)
        {
            mx=max(mx, nums[j]);
        }
        
        for(int j=0; j<nums.size(); j++)
        {
            if(nums[j]==mx)
            {
                f++;
            }

            while(f>=k)
            {
                cnt += nums.size()-j;           // nums.size()-j ae i start thata valid subarr. ape

                if(nums[i]==mx)
                {
                    f--;
                }

                i++;
            }
        }

        return cnt;
        */
    }
};
130400