Subarrays with Distinct Values
Given an array of n
integers, you are asked to calculate the number of subarrays that have at most k
distinct characters.
Input
The first line of the input contains two integers n
and k
(1 ≤ k ≤ n ≤ ).
The next line contains n
space-separated integers (1 ≤ ≤ ).
Output
The program should print the number of subarrays that have at most k
distinct values.
Examples
Input | Output |
---|---|
5 2 2 3 4 2 2 | 10 |
Explanation
2
, 3
, 4
, 2
, 2
, 2 3
, 3 4
, 4 2
, 2 2
, 4 2 2
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 1 MB