<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>good</strong> subarrays of</em> <code>nums</code>.</p>

<p>A subarray <code>arr</code> is <strong>good</strong> if it there are <strong>at least </strong><code>k</code> pairs of indices <code>(i, j)</code> such that <code>i &lt; j</code> and <code>arr[i] == arr[j]</code>.</p>

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

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

<pre>
<strong>Input:</strong> nums = [1,1,1,1,1], k = 10
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only good subarray is the array nums itself.
</pre>

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

<pre>
<strong>Input:</strong> nums = [3,1,4,3,2,2,4], k = 2
<strong>Output:</strong> 4
<strong>Explanation:</strong> There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.
</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], k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:

    '''
    (2)6 + (3)3+ (1)3
                       910
    [2,1,3,1,2,2,3,3,2,2,1,1,1,3,1]
     l                 r 
       l.                r
         l                 r
           l.              r
    ans = 6 + 5 + 4

    10 + 3  + 1
    3 + 6 + 3 = 12
    3,1,2,2,3,3,2,2,1,1 = 3 + 6 + 3
    '''

    def countGood(self, nums: List[int], k: int) -> int:
        
        n = len(nums)
        print(n)
        C = [0] * (n+3)
        C[2] = 1
        # C(i+1,2) = C(i,2)*[(i+1)/(i-1)]
        for i in range(2,n+1):
            C[i+1] = C[i]*(i+1)//(i-1)

        freq = defaultdict(int)
        l = r = cnt = ans = 0
        freq[nums[l]] += 1

        while r < n - 1:
            while r < n - 1 and cnt < k:
                r += 1
                cnt = cnt - C[freq[nums[r]]] + C[freq[nums[r]] + 1]
                freq[nums[r]] += 1
            if cnt >= k:
                ans += (n - r)
            # print('1',ans, l, r)
            while cnt >= k:
                # print("CNT BEFORE", cnt, freq)
                cnt = cnt - C[freq[nums[l]]] + C[freq[nums[l]]-1]
                freq[nums[l]] -= 1
                l += 1
                if cnt >= k:
                    # print("GO", cnt)
                    ans += (n - r)
            # print('2',ans,l,r)
        return ans
625