题目描述

题目译自 Open Olympiad in Informatics 2024 Day1 T3 「Больше подарков хороших и разных / More Gifts」。

封闭编程奥林匹克竞赛的组织者决定为参赛者准备礼物。他们订购了 $k$ 个相同的礼物盒，每个盒子内有一叠 $n$ 个礼物。每个盒子顶部的礼物类型为 $a_1$，其下为类型 $a_2$，以此类推，最底部的礼物类型为 $a_n$。

礼物分发将按照以下方式进行：首先从第一个盒子中自上而下分发礼物。当第一个盒子中的礼物分发完毕后，开始从第二个盒子自上而下分发礼物，依此类推，最后从第 $k$ 个盒子分发礼物。

可以一次性分发多个礼物给一名参赛者，因此礼物将首先分发给第一名参赛者，然后是第二名参赛者，以此类推。已知如果一名参赛者获得的礼物类型超过 $t$ 种，他们会过于高兴，从而影响奥林匹克竞赛的表现。为了确保参赛者在比赛中表现出色，决定每名参赛者获得的礼物类型不超过 $t$ 种（但可以获得多个相同类型的礼物）。

封闭式奥林匹克竞赛的组织者希望使比赛尽可能独家化，邀请尽可能少的参赛者。帮助组织者确定最少需要邀请多少名参赛者，以便分发所有礼物，并且每名参赛者获得的礼物类型不超过 $t$ 种。

输入格式

第一行包含三个整数 $n, k, t$ $(1 \leq n \leq 300000, 1 \leq k, t \leq 10^{9})$，分别表示每个盒子中的礼物数量、盒子数量和每名参赛者最多可获得的礼物类型数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq 10^{9})$，表示礼物类型，从盒子顶部到底部的顺序。

输出格式

输出一个整数，即最少需要的参赛者数量，使得所有礼物都能被分发，且每名参赛者获得的礼物类型不超过 $t$ 种。

2 4 1
1 2

8

在第一个样例中，每个盒子包含的礼物类型（从上到下）如下，颜色不同表示盒子中的不同位置：

共有 $4$ 个盒子，礼物将按以下顺序分发：

由于 $t = 1$，每名参赛者只能获得一种类型的礼物：

4 3 1
1 1 2 1

7

在第二个样例中，礼物分发顺序和最终的礼物套装如下：

7 2 3
1 2 3 4 5 6 7

5

在第三个样例中，礼物分发顺序如下：

一种可能的最优分发方案如下：

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。