You are given an integer array a of length n and an integer k. Count the number of contiguous subarrays of a that contain exactly k distinct integer values.
A subarray is defined by a start and end position a[l..r] with l ≤ r; the number of distinct values in it is the size of the set of values it contains. Count how many such subarrays have exactly k distinct values.
Input format
Line 1: two integers n and k, separated by a space.
Line 2: n space-separated integers a[0] … a[n-1]. If n == 0, this line is empty or absent.
Output format
A single integer: the number of contiguous subarrays containing exactly k distinct values.
Constraints
- 0 ≤ n ≤ 100000
- 0 ≤ k ≤ n
- 1 ≤ a[i] ≤ 1000000000
- The answer can be large; it fits in a 64-bit signed integer.
- When
k == 0the answer is 0, because any non-empty subarray has at least one distinct value.