Background

Translated from NordicOI 2023 Problem B Ice Cream Machines。

Problem Description

In your ice cream shop, there are $n$ customers waiting in a line. The shop offers $m$ flavors in total. Everyone has a flavor they want to buy, but unfortunately, the shop only has $k$ machines and cannot provide all flavors at the same time. Therefore, if the next customer wants a flavor different from the one currently in a machine, they must clean that machine and switch it to their preferred flavor.

Now these $n$ people buy ice cream in order from $1 \sim n$. As a very smart shop owner, you need to decide which machine each person should use so that the number of cleanings is minimized. Output this minimum number.

Note: If a machine has not been used by anyone before, it is considered to require cleaning by default (if it is never used at all from start to finish, then no cleaning is needed).

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 that there are $n$ people in total, the shop has $m$ ice cream flavors, and there are $k$ machines.

Then follow $n$ lines, each containing an integer $c_i (1 \leq c_i \leq m)$, indicating the flavor ID liked by the $i$-th person.

Output Format

Output the minimum number of cleanings required.

8 3 1
2
3
3
1
2
1
1
3

6

8 3 2
2
3
3
1
2
1
1
3

4

Hint

This problem uses bundled testdata.

• 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 additional constraints.

For all testdata, $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$.

Translated by ChatGPT 5