Subarrays with K Different Integers

Problem statement

A reading application records a category number for each article opened. Its analyst counts consecutive reading sessions that include exactly k different categories, regardless of how often any category repeats within a session. Your task Count all nonempty contiguous subarrays with exactly k distinct integers. Important details Subarrays with different boundaries count separately. Repeating an existing category does not increase the distinct count. A session with fewer or more than k categories must not be included. Use a window or equivalent efficient counting approach. Worked example For [1, 2, 1] and k = 2, the valid sessions are positions 0..1, 1..2 and 0..2. The answer is 3.

Input format

First line: n k. Next line: n category values.

Output format

Print the number of qualifying subarrays.

Constraints

1 <= k <= n <= 20000; 1 <= values <= n; use 64-bit counts.

Sample input

3 2
1 2 1

Sample output

3