548. K-Distinct subarrays
0
Hard
A subarray is called **K-Distinct Subarray** if it contains **atmost** **k** distinct elements.
You are given an array of **n** integers and a value **k** , your task is to calculate the number of **K-Distinct subarrays** that have at most **k** distinct values.
You are given an array of **n** integers and a value **k** , your task is to calculate the number of **K-Distinct subarrays** that have at most **k** distinct values.
Input Format
First line contains two space separated integers n and k .
Second line contains an integer array.
Second line contains an integer array.
Output Format
Print total number of K-distinct subarrays.
Example
Input
5 2
1 2 3 1 1
Output
10
Constraints
1 <= k , n <= 105
1 <= arr[i] <= 109
1 <= arr[i] <= 109
Loading...
View Submissions
Console