[NordicOI 2023] Ice Cream Machines

在你的冰淇淋店里有 $n$ 个顾客在排队，店里一共有 $m$ 种口味，每个人都有想买的口味，但是很不幸，店内只有 $k$ 台机子，无法完全供应所有的口味，所以，如果下一个人要的和这台机子内原有的口味不同时，他需要清洗这台机子并更换成他喜欢的口味。 现在这 $n$ 个人按照从 $1 \sim n$ 的顺序买冰淇淋，你作为一个聪明绝顶的店主需要合理安排他们使用哪台机子，使得清洗机子的次数最少，输出这个最少次数。 注意一台机子如果之前没人用的时候默认需要被清洗（自始至终没人用则不需要）。 ## Input 第一行三个整数 $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$ 个人喜欢吃的口味编号。 ## Output 输出清洗次数最少时所需的次数。 [samples] ## Background 翻译自 [NordicOI 2023 B 题](https://noi23.kattis.com/contests/noi23/problems/icecreammachines) Ice Cream Machines。 ## Note **本题采用捆绑测试**。 - 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$。