Enumerating Narrative Sections

Given an integer array bucket and a positive integer k, count the non-empty contiguous subarrays that contain at least k pairs of equal numbers. Each pair consists of two elements at different indices with the same value; different pairs cannot share an index. So a value that appears c times contributes at most floor(c/2) pairs.

Site constraints: 1≤N≤200000, 1≤k≤200000, -10^9≤bucket[i]≤10^9. The numeric ranges are the ranges this site supports.

输入格式

The first line contains N and k; the second line contains N integers bucket[i].

输出格式

Output the number of qualifying contiguous subarrays.

样例 1

输入：

5 2
0 1 0 1 0

输出：

3

样例说明

Track how many times each value occurs in the sliding window, and let pairs be the sum of floor(freq/2) over all values. After adding a value, if its count becomes even, pairs increases by one; once the window reaches k pairs, every end position further right for the current left endpoint also qualifies, so count N-right subarrays at once, then remove the current leftmost element and keep shrinking.