题目描述

题目译自 BalticOI 2021 Day2「The short shank; Redemption」，译者 Shuchong。

你入狱了，你现在正在 LOJ 第一监狱里。

监狱共有 $N$ 个牢房，从左到右编号为 $1 \sim N$。你和你的狱友们准备策划一场造反，第 $i$ 个牢房里的罪犯准备在第 $t_i$ 个时刻点造反，如果第 $i$ 个牢房的罪犯造反后，第 $i+1$ 个牢房的罪犯会无视他在第 $t_{i+1}$ 个时间点造反的规矩，在第 $t_i+1$ 个时间点就会造反。

狱警提前预知了一切，所以他们会放置 $D$ 个床垫，如果在第 $i$ 个牢房和第 $i+1$ 个牢房中间放置一个床垫，那么当第 $i$ 个牢房的罪犯造反时，第 $i+1$ 个牢房的罪犯不会立即造反，而会等到第 $t_{i+1}$ 个时间点。

你想知道，狱警合理安排床垫后，在第 $T$ 个时间点及以前最少会有多少个罪犯造反。

输入格式

第一行三个整数 $N,D,T$ 代表罪犯个数，床垫个数和希望的时间点。

第二行 $N$ 个整数 $t_i$ 代表第 $i$ 个罪犯造反的时间点。

输出格式

一行一个整数代表答案。

5 1 42
13 37 47 11 42

4

5 2 5
1 9 4 6 7

2

数据范围与提示

本题采用捆绑测试。

• Subtask 1（15 pts）：$N \le 500$。
• Subtask 2（10 pts）：$N \le 5 \times 10^5$，$D=1$。
• Subtask 3（20 pts）：$N \le 4000$。
• Subtask 4（10 pts）：$N \le 7.5 \times 10^4$，$D \le 15$。
• Subtask 5（25 pts）：$N \le 7.5 \times 10^4$。
• Subtask 6（20 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le D<N \le 2 \times 10^6$，$1 \le T,t_i \le 10^9$。