P8125 [BalticOI 2021] The short shank (Day2)

你入狱了，你现在正在洛谷第一监狱里。 监狱共有 $N$ 个牢房，从左到右编号为 $1 \sim N$。你和你的狱友们准备策划一场造反，第 $i$ 个牢房里的罪犯准备在第 $t_i$ 个时刻点造反，如果第 $i$ 个牢房的罪犯造反后，第 $i+1$ 个牢房的罪犯会无视他在第 $t_{i+1}$ 个时间点造反的规矩，在第 $t'_i+1$ 个时间点就会造反，其中 $t'_i$ 是第 $i$ 个牢房的罪犯实际造反的时刻。 狱警提前预知了一切，所以他们会放置 $D$ 个床垫，如果在第 $i$ 个牢房和第 $i+1$ 个牢房中间放置一个床垫，那么当第 $i$ 个牢房的罪犯造反时，第 $i+1$ 个牢房的罪犯不会立即造反，而会等到第 $t_{i+1}$ 个时间点。 你想知道，狱警合理安排床垫后，在第 $T$ 个时间点及以前最少会有多少个罪犯造反。

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

一行一个整数代表答案。

#### 样例 1 解释 最优解是在第 $2$ 个牢房和第 $3$ 个牢房之间放入床垫，造反的是第 $1,2,4,5$ 个牢房里的罪犯。 #### 数据规模与约定 **本题采用捆绑测试。** - 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