A birdwatcher writes down the species code of every bird she sees, in order, in the list log. A stretch is any run of consecutive entries log[i..j] (with i <= j). A stretch is lively if it contains at least k matching pairs: pairs of positions p < q inside the stretch with log[p] == log[q].
Return the number of lively stretches. Stretches at different positions count separately.
Examples
Input: log = [3, 1, 4, 1, 3, 1], k = 2
Output: 3
Explanation: log[0..4] has pairs (3,3) and (1,1): 2 pairs.
log[1..5] has three 1s: 3 pairs. log[0..5] has 4 pairs.
Every other stretch has at most 1 pair.
Input: log = [2, 2, 2, 2], k = 3
Output: 3
Explanation: [2, 2, 2] (twice) has 3 pairs, [2, 2, 2, 2] has 6.
Input: log = [5, 6, 7], k = 1
Output: 0
Constraints
0 <= len(log) <= 10**51 <= k <= 10**100 <= log[i] <= 10**9- Target complexity: O(n). Checking every stretch (O(n²) or worse) is too slow for the largest tests.
Goals
- Update a pair count in O(1) when one element enters or leaves a window
- Count every valid window by finding, for each right edge, how many left edges work