题目描述

封闭编程奥林匹克竞赛的组织者决定为参赛者准备礼物。他们订购了 $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 3 1
1 1 2 1

7

7 2 3
1 2 3 4 5 6 7

5

数据范围与提示

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