题目描述

小蓝正在收集一本贴纸册。贴纸共有 $N$ 种，编号为 $1, 2, \dots, N$。他会按顺序得到 $M$ 张贴纸，第 $i$ 张贴纸的编号为 $A_i$。

处理一张贴纸时：

• 如果小蓝还没有收集过编号为 $A_i$ 的贴纸，就把这张贴纸贴进贴纸册；
• 如果小蓝已经收集过编号为 $A_i$ 的贴纸，这张重复贴纸会变成 $1$ 张交换券。

每当交换券数量达到 $K$ 张时，小蓝必须立刻消耗 $K$ 张交换券，换得当前编号最小且尚未收集的贴纸，并把它贴进贴纸册。

如果小蓝已经收集齐全部 $N$ 种贴纸，之后得到的贴纸不会再改变已收集的贴纸种类数。

请你计算处理完全部 $M$ 张贴纸后，小蓝一共收集到了多少种贴纸。

输入格式

第一行包含三个整数 $N, M, K$，分别表示贴纸种类数、得到的贴纸张数和每次兑换需要的交换券数量。

第二行包含 $M$ 个整数 $A_1, A_2, \dots, A_M$，表示小蓝按顺序得到的贴纸编号。

输出格式

输出一行，包含一个整数，表示处理完全部贴纸后小蓝收集到的贴纸种类数。

6 10 3
2 4 2 2 5 4 1 3 3 6

6

5 7 2
4 4 2 4 2 5 5

5

提示

【样例说明 1】

前两张贴纸编号为 $2, 4$，都可以直接贴进贴纸册。第 $3$ 张和第 $4$ 张贴纸编号都是 $2$，属于重复贴纸，因此得到 $2$ 张交换券。

第 $5$ 张贴纸编号为 $5$，直接贴进贴纸册。第 $6$ 张贴纸编号为 $4$，又得到 $1$ 张交换券，此时共有 $3$ 张交换券，必须立刻兑换。当前尚未收集的最小编号为 $1$，因此换得编号为 $1$ 的贴纸。

之后继续处理剩余贴纸，最终可以收集齐编号 $1$ 到 $6$ 的全部贴纸，答案为 $6$。

【样例说明 2】

第 $2$ 张和第 $4$ 张贴纸都与已经收集的编号 $4$ 重复。在处理第 $4$ 张贴纸后共有 $2$ 张交换券，必须兑换当前最小缺失贴纸 $1$。

后面编号 $2$ 和编号 $5$ 的重复贴纸又产生 $2$ 张交换券，最终兑换得到编号 $3$ 的贴纸。处理完后，$1,2,3,4,5$ 均已收集，答案为 $5$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$N, M \le 200$。

对于 $60\%$ 的评测用例，$N, M \le 5000$。

对于所有评测用例，$1 \le N, M, K \le 2 \times 10^5$，$1 \le A_i \le N$。