Problem Description

In your ice cream shop, there are $n$ customers in line, and the shop offers $m$ flavors. Each customer has a preferred flavor, but unfortunately, there are only $k$ machines available, which cannot accommodate all flavors. Therefore, if a customer's desired flavor is different from the current flavor in a machine, the machine needs to be cleaned and switched to the customer's preferred flavor.

These $n$ customers will buy ice cream in the order from $1$ to $n$. As a clever shop owner, you need to arrange which machine each customer uses to minimize the number of machine cleanings. Output the minimum number of cleanings required.

Note that a machine, if not used before, is considered to need cleaning (unless it remains unused throughout).

Input Format

The first line contains three integers $n (1 \leq n \leq 2 \times 10^5)$, $m (1 \leq m \leq 2 \times 10^5)$, and $k (1 \leq k \leq 2 \times 10^5)$, representing the number of customers, the number of ice cream flavors, and the number of machines, respectively.

The following $n$ lines each contain an integer $c_i (1 \leq c_i \leq m)$, indicating the flavor number that the $i$-th customer prefers.

Output Format

Output the minimum number of cleanings required.

Sample Input and Output

Sample Input #1

8 3 1
2
3
3
1
2
1
1
3

Sample Output #1

6

Sample Input #2

8 3 2
2
3
3
1
2
1
1
3

Sample Output #2

4

Notes/Hints

This problem uses batched testing.

• Subtask 1 (7 points): $n \le 1000$, $m \leq 10$, $k = 1$.
• Subtask 2 (12 points): $n \le 1000$, $m \leq 10$, $k \leq 2$.
• Subtask 3 (22 points): $n \leq 1000$, $m \leq 10$, $k \leq 5$.
• Subtask 4 (11 points): $n \leq 1000$, $m \leq 200$, $k \leq 100$.
• Subtask 5 (14 points): $n \leq 2 \times 10^5$, $m \leq 500$, $k \leq 100$.
• Subtask 6 (13 points): $n \leq 2 \times 10^5$, $m \leq 2 \times 10^5$, $k \leq 100$.
• Subtask 7 (21 points): No special restrictions.

For all test data, $1 \le n \le 2 \times 10^5$, $1 \leq m \leq 2 \times 10^5$, $1 \leq k \leq 2 \times 10^5$, $1 \leq c_i \leq m$.

见题面 Input 部分

见题面 Output 部分