Rebellion in the Prison

You are in prison – specifically, in the first prison of Luogu. There are \(N\) cells numbered \(1\) to \(N\) from left to right. In cell \(i\) the prisoner is scheduled to start a rebellion at time \(t_i\). However, if the prisoner in cell \(i\) revolts, then, provided there is no mattress placed between cell \(i\) and cell \(i+1\), the prisoner in cell \(i+1\) will ignore his scheduled time \(t_{i+1}\) and instead revolt at time \(r_{i+1} = r_{i}+1\) (where \(r_i\) is the actual revolt time in cell \(i\)).

The prison guards, having foreknowledge of the planned insurrection, will place \(D\) mattresses – each mattress is placed in the gap between two adjacent cells. If a mattress is placed between cells \(i\) and \(i+1\), then when the prisoner in cell \(i\) revolts, the prisoner in cell \(i+1\) will not be triggered early; he will revolt at his original scheduled time \(t_{i+1}\).

Your task is to determine, given that the guards arrange the mattresses optimally, what is the minimum number of prisoners who will have revolted by time \(T\) (i.e. at or before time \(T\)).

Important details:

• For cell 1, the actual revolt time \(r_1\) is \(t_1\).
• For cell \(i\) (\(i \ge 2\)):
  If there is no mattress between cell \(i-1\) and cell \(i\), then \[ r_i = \begin{cases} r_{i-1}+1, & \text{if } r_{i-1}+1 < t_i,\\ t_i, & \text{otherwise.} \end{cases} \]
  If a mattress is placed between cell \(i-1\) and cell \(i\), then \(r_i = t_i\) (i.e. the chain reaction is broken).
• Each prisoner will revolt at his actual revolt time. Count him if \(r_i \le T\).

You are given \(N\), \(D\), \(T\) and the list \(t_1, t_2, \dots, t_N\). Compute the minimum number of prisoners (cells) that have \(r_i \le T\) after the guards have placed \(D\) mattresses optimally.

inputFormat

The first line contains three integers \(N\), \(D\), and \(T\).

The second line contains \(N\) integers \(t_1, t_2, \dots, t_N\), where \(t_i\) is the scheduled time for the prisoner in cell \(i\) to start his rebellion.

outputFormat

Output a single integer: the minimum number of prisoners that will have revolted by time \(T\) (i.e. with \(r_i \le T\)) considering optimal mattress placement.

sample

3 1 4
3 5 6

1