题目描述

本月有 $n$ 名学生参加考试，第 $i$ 名学生来自编号为 $c_i$ 的城市。

考试使用编号为 $1,2,3,\ldots$ 的若干考场。学生必须按照到达顺序安排：

如果学生 $i$ 被安排到考场 $x$，那么任何后来的学生 $j>i$ 都只能被安排到编号 $y\ge x$ 的考场。

除此之外，每个考场人数可以任意不同。

如果每个考场中，来自同一个城市的学生人数都不超过 $m$，则称本次考试安排是公平的。

委员会希望使用尽量少的考场。为了改善安排，它还可以把至多 $k$ 名学生的考试延期，这些学生本次不参加考试。

求进行公平考试所需的最少考场数。

输入格式

第一行三个整数 $n,m,k$：

• $1\le m\le n\le50000$；
• $0\le k\le\min(n,400)$。

第二行 $n$ 个整数 $c_1,c_2,\ldots,c_n$，其中 $1\le c_i\le n$。

输出格式

输出一个整数，表示最少需要准备多少个考场。

样例 1

8 2 1
1 1 2 2 1 2 2 2

2

一种最优方式是延期第 6 名学生。此时前 4 名学生进入第一个考场，最后 3 名学生进入第二个考场。

样例 2

5 1 0
3 3 3 3 3

5

子任务