事情的发展确实没按计划进行：虽然你成功避开了博物馆的保安，但你没注意到到处都是监控摄像头。结果，你作为艺术大盗的首次亮相彻底搞砸了：你被捕并被判入狱。
因为监狱里的 WiFi 信号极差，你想要越狱。从许多监狱题材的影视剧中，你知道制造混乱对于任何越狱计划都至关重要。因此，你决定策划一场监狱暴动作为掩护。
监狱的牢房沿一条走廊排列。最左侧的牢房编号为 1，其右侧紧邻的牢房编号为 2，以此类推。不幸的是，并非所有囚犯都会按计划参与暴动。但你可以确保第 $i$ 号牢房的囚犯计划在时间 $t_i$ 开始暴动，即从现在起正好 $t_i$ 秒后。此外，每当一名囚犯听到他左侧紧邻的囚犯开始暴动时，他也会在仅仅一秒后开始暴动（当然，如果他已经在暴动则除外）。一旦开始暴动，囚犯就不会停止。
在时间 $T$，当地 F.R.U.IT.T.Ar.T.* 代表将前来视察。你认为这是越狱的最佳时机。然而，监狱看守不会乐见在视察期间发生暴动。你担心他们会使用 $D$ 个隔音床垫，这些床垫可以安装在牢房之间。如果在第 $i-1$ 号牢房和第 $i$ 号牢房之间安装了这样的床垫，那么无论第 $i-1$ 号牢房（或其他任何囚犯）的行动如何，第 $i$ 号牢房的囚犯在时间 $t_i$ 之前都不会开始暴动。
编写一个程序来帮助你评估成功的几率：如果看守以最优方式放置床垫，请计算在时间 $T$ 暴动的囚犯的最少人数。
输入格式
第一行包含三个整数 $N$、$D$ 和 $T$：牢房数量、床垫数量以及代表到达的时间。
第二行包含 $N$ 个整数 $t_i$，其中 $t_i$ 描述了第 $i$ 号牢房的囚犯计划开始暴动的时间。
输出格式
输出仅包含一个整数：在时间 $T$ 暴动的囚犯的最少人数。
数据范围
对于所有测试用例，始终满足 $1 \le N, D \le 2\,000\,000$，$1 \le T \le 10^9$，以及 $1 \le t_i \le 10^9$（对于所有 $i = 1, \dots, N$）。此外，$D < N$。
- 子任务 1（15 分）：$N \le 500$
- 子任务 2（10 分）：$N \le 500\,000$，$D = 1$
- 子任务 3（20 分）：$N \le 4\,000$
- 子任务 4（10 分）：$N \le 75\,000$，$D \le 15$
- 子任务 5（25 分）：$N \le 75\,000$
- 子任务 6（20 分）：无其他限制。
样例
样例输入 1
5 1 42 13 37 47 11 42
样例输出 1
4
说明 1
第一个样例的最优解如下：在第二间和第三间牢房之间放置一个床垫。在这种情况下，第一、第二、第四和第五名囚犯将参与暴动。
样例输入 2
5 2 5 1 9 4 6 7
样例输出 2
2
* 联邦不快乐 IT 专家转行艺术大盗登记处 (The Federal Registry for Unhappy IT experts Turned Art Thieves)