K-Distinct Windows

Given an array $a$ of $n$ integers, count how many contiguous subarrays of length exactly $x$ contain at least $k$ distinct values.

Input

The first line contains three integers $n$, $x$, and $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$.

Output

Print a single integer: the number of contiguous subarrays of length exactly $x$ that contain at least $k$ distinct values.

Constraints

• $1 \le k \le x \le n \le 2 \cdot 10^5$
• $-10^9 \le a_i \le 10^9$

Example 1

8 4 3
1 1 2 3 2 2 1 4

4

Explanation

The five subarrays of length $4$ are:

• $[1, 1, 2, 3]$, which has $3$ distinct values;
• $[1, 2, 3, 2]$, which has $3$ distinct values;
• $[2, 3, 2, 2]$, which has $2$ distinct values;
• $[3, 2, 2, 1]$, which has $3$ distinct values;
• $[2, 2, 1, 4]$, which has $3$ distinct values.

So the answer is $4$.