题目描述

Arnar 非常喜欢冰淇淋。今天是个适合出门买冰淇淋的好天气，于是他冒着暴风雪前往自己最喜欢的冰淇淋店。

到了店里，他惊讶地发现前面的队伍异常短：他只是第 $n$ 个等待点单的人。

这家冰淇淋店提供 $m$ 种不同口味，并且有 $k$ 台冰淇淋机器。

每台机器同一时刻只能供应一种口味。如果一台机器要改成供应另一种口味，就必须先清洗机器。清洗机器需要时间，因此 Arnar 想帮助店员决定：每当需要一种当前没有机器供应的口味时，应该清洗哪一台机器，从而最小化总清洗次数。

幸运的是，冰岛很小，Arnar 认识队伍里的每一个人，也知道他们各自想要的冰淇淋口味。商店严格按照排队顺序服务，不允许插队。

一开始所有机器都是空的。如果某台机器第一次被装入某种口味，也需要清洗一次。没有被使用过的机器不需要清洗。

一台机器装入某种口味后，可以连续服务任意多个需要该口味的顾客，直到它被清洗并换成另一种口味。

请你求出服务完队伍中所有 $n$ 位顾客所需的最少清洗次数。

输入格式

第一行输入三个整数 $n,m,k$，分别表示顾客数量、口味数量和冰淇淋机器数量。

接下来 $n$ 行，第 $i$ 行输入一个整数 $c_i$，表示第 $i$ 位顾客想要的口味，满足 $1\le c_i\le m$。

输出格式

输出一个整数，表示为了服务所有顾客，冰淇淋机器需要被清洗的最少总次数。

样例 1

输入

8 3 1
2
3
3
1
2
1
1
3

输出

6

样例 2

输入

8 3 2
2
3
3
1
2
1
1
3

输出

4

数据范围与计分

难度评估

• 主要知识点：贪心，缓存替换，优先队列，预处理下一次出现位置。
• 信息学难度：提高+/省选-。
• Codeforces 参考评分：约 1700~1900。

这题本质上是经典的缓存替换问题。当前需要的口味如果已经在机器中，则不需要清洗；否则需要清洗一次。如果机器已满，最优策略是清洗掉“下一次使用时间最晚”的口味；如果某个口味以后不会再出现，则优先清洗它。用优先队列维护当前机器中各口味的下一次出现位置即可做到 $O(n\log n)$。