P8125 [BalticOI 2021] The short shank (Day2)

You are in prison, and you are now in Luogu Prison No. 1. The prison has $N$ cells, numbered from left to right as $1 \sim N$. You and your fellow prisoners are planning a rebellion. The prisoners in cell $i$ plan to rebel at time $t_i$. If the prisoners in cell $i$ rebel, then the prisoners in cell $i+1$ will ignore their rule of rebelling at time $t_{i+1}$ and will instead rebel at time $t'_i + 1$, where $t'_i$ is the actual time when the prisoners in cell $i$ rebel. The guards know everything in advance, so they will place $D$ mattresses. If a mattress is placed between cell $i$ and cell $i+1$, then when the prisoners in cell $i$ rebel, the prisoners in cell $i+1$ will not rebel immediately, and will wait until time $t_{i+1}$. You want to know: after the guards arrange the mattresses in the best way, what is the minimum number of prisoners that will rebel at or before time $T$.

The first line contains three integers $N, D, T$, representing the number of prisoners, the number of mattresses, and the target time. The second line contains $N$ integers $t_i$, representing the planned rebellion time of the prisoner in cell $i$.

Output one integer in one line, representing the answer.

#### Explanation of Sample 1 The optimal solution is to place a mattress between cell $2$ and cell $3$. Then the prisoners in cells $1, 2, 4, 5$ will rebel. #### Constraints **This problem uses bundled testdata.** - 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): No special constraints. For $100\%$ of the data, $1 \le D < N \le 2 \times 10^6$, $1 \le T, t_i \le 10^9$. There is also Subtask 0 as the sample. #### Notes Translated from [BalticOI 2021 Day2 A The short shank](https://boi.cses.fi/files/boi2021_day2.pdf)。 Translated by ChatGPT 5