Subarrays with at Least K Duplicate Pairs

Given an integer array numbers and a positive integer k, count the contiguous subarrays that contain at least k pairs of equal-valued elements. Each pair uses two indices, and indices of different pairs must be pairwise distinct; an element cannot belong to two pairs at once.

输入格式

The first line contains n k; the second line contains n integers. Ranges added by this site: 1≤n≤200000, 1≤k≤10^9, |numbers[i]|≤10^9. When k exceeds the number of pairs the array can provide, the answer is 0.

输出格式

Output the number of contiguous subarrays that satisfy the condition.

样例 1

输入：

5 2
0 1 0 1 0

输出：

3

样例 2

输入：

6 3
2 2 2 2 2 2

输出：

1

样例 3

输入：

4 1
1 3 3 1

输出：

4