Count Subarrays with Exactly K Distinct Elements

You are given an array of n integers and a positive integer k. Your task is to count the number of contiguous subarrays that contain exactly k distinct elements.

For example, if the input array is [1, 2, 1, 2, 3] and k = 2, the answer is 7. This is because there are 7 subarrays that contain exactly 2 distinct numbers.

It is recommended to use an efficient sliding window approach to solve this problem. The trick is to count the number of subarrays with at most k distinct elements and then subtract the number of subarrays with at most k-1 distinct elements. The final result is:

The program should read input from stdin and print the output to stdout.

inputFormat

The input consists of two lines. The first line contains two integers n and k separated by a space, where n is the number of elements in the array and k is the required number of distinct elements. The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the number of contiguous subarrays that contain exactly k distinct elements.## sample

5 2
1 2 1 2 3

7