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 2Constraints
Time limit: 4.8 seconds
Memory limit: 512 MB
Output limit: 1 MB