Description

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$.

Input Format

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 Format

Output one integer in one line, representing the answer.

5 1 42
13 37 47 11 42

4

5 2 5
1 9 4 6 7

2

Hint

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。

Translated by ChatGPT 5