Count the Number of Good Subarrays

A pair means two distinct indices i<j within the subarray whose elements are equal. Count the non-empty contiguous subarrays that contain at least k pairs.

This site's standard input/output is stated explicitly.

输入格式

The first line contains n k, and the second line contains n elements; 1≤n≤100000, 1≤a[i],k≤10⁹.

输出格式

Output one integer answer.

样例 1

输入：

5 10
1 1 1 1 1

输出：

1

样例 2

输入：

7 2
3 1 4 3 2 2 4

输出：

4

样例 3

输入：

3 1
1 2 3

输出：

0

样例说明

Example 1: the whole array has exactly 10 pairs, and every shorter range has too few, so the answer is 1. Example 2: the valid ranges are indices [0,5], [0,6], [1,6], and [2,6], so the answer is 4. Example 3: the elements are distinct and there are no equal pairs, so the answer is 0.