背景

翻译自 NordicOI 2023 B 题 Ice Cream Machines。

题目描述

在你的冰淇淋店里有 $n$ 个顾客在排队，店里一共有 $m$ 种口味，每个人都有想买的口味，但是很不幸，店内只有 $k$ 台机子，无法完全供应所有的口味，所以，如果下一个人要的和这台机子内原有的口味不同时，他需要清洗这台机子并更换成他喜欢的口味。

现在这 $n$ 个人按照从 $1 \sim n$ 的顺序买冰淇淋，你作为一个聪明绝顶的店主需要合理安排他们使用哪台机子，使得清洗机子的次数最少，输出这个最少次数。

注意一台机子如果之前没人用的时候默认需要被清洗（自始至终没人用则不需要）。

输入格式

第一行三个整数 $n (1 \leq n \leq 2 \times 10^5)$，$m (1 \leq m \leq 2 \times 10^5)$ 和 $k (1 \leq k \leq 2 \times 10^5)$，分别表示一共有 $n$ 个人，店里有 $m$ 种口味的冰淇淋和 $k$ 台机子。

然后 $n$ 行，每行一个整数 $c_i (1 \leq c_i \leq m)$，表示第 $i$ 个人喜欢吃的口味编号。

输出格式

输出清洗次数最少时所需的次数。

8 3 1
2
3
3
1
2
1
1
3

6

8 3 2
2
3
3
1
2
1
1
3

4

提示

本题采用捆绑测试。

• 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）：无特殊限制。

对于所有测试数据，$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$。