题目描述

你在空闲时间研究 CPU 的底层优化。

现在有 $n$ 个任务正在队列中等待 CPU 时间。每个任务都有一个类型。你的 CPU 在同一批次中最多只能处理 $m$ 个相同类型的任务，否则可能造成不可逆的损坏。

你需要将所有任务划分成若干批次，使得每个批次都是当前队列中的一个连续区间，并且在任意一个批次中，同一类型的任务出现次数不超过 $m$。

为了进一步优化摊还处理时间，你决定可以放弃最多 $k$ 个任务。这些任务会被从队列中完全删除，不再参与之后的划分。

请在允许删除最多 $k$ 个任务后，求处理剩余所有任务所需的最少批次数量。

输入格式

第一行包含三个整数：

分别表示任务数量、每个批次中同一类型任务的最大允许数量、最多可删除的任务数量。

第二行包含 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示队列中第 $i$ 个任务的类型。

输出格式

输出一个整数，表示最少需要划分出的批次数量。

数据范围

• $1 \le m \le n \le 5\times 10^4$；
• $0 \le k \le \min(n,400)$；
• $1 \le a_i \le n$。

子任务

只有通过该子任务及其依赖子任务的全部测试，才能获得该子任务分数。

样例 1

输入

8 2 1
1 1 2 2 1 2 2 2

输出

2

说明

删除队列中的第 $6$ 个任务后，剩余任务可以分成两批：

• 第一批为原队列中的前 $4$ 个任务；
• 第二批为原队列中的第 $5,7,8$ 个任务。

样例 2

输入

5 1 0
3 3 3 3 3

输出

5

说明

不能删除任何任务，并且每批中相同类型最多出现 $1$ 次，因此这 $5$ 个任务必须分别成批。