5669: Segments with Small Set
[Creator : ]
Description
Given an array of $n$ integers $a_i$. Let's say that a segment of this array $a[l..r]\ (1≤l≤r≤n)$ is good if there are no more than $k$ unique elements on this segment.
Your task is to find the number of different good segments.
求有小于等于k种不同值的子段个数
Your task is to find the number of different good segments.
求有小于等于k种不同值的子段个数
Input
The first line contains integers $n,\ k\ (1≤n≤10^5,\ 0≤k≤n)$.
The second line contains integers $a_i\ (1≤a_i≤10^5)$.
The second line contains integers $a_i\ (1≤a_i≤10^5)$.
Output
Print one integer, the number of good segments.
Sample 1 Input
7 3
2 6 4 3 6 8 3
Sample 1 Output
20
Sample 2 Input
5 3
8 8 8 8 8
Sample 2 Output
15