Woburn Challenge 2016-17 Round 2 - Junior Division

"Please state the nature of the culinary emergency!" exclaims the Enterprise's EHC (Emergency Holographic Chef), having just been activated. It seems that Lieutenant Commander Le Ferge is extremely hungry, and will need to be brought a hot meal, stat!

The EHC is currently in the mess hall, and will need to make his way to the bridge to save Le Ferge. The bridge is at the end of a hallway, which is $M$ $(1\le M\le {10}^9)$ metres long. There's just one complication - being a hologram, the EHC must remain within a distance of $R$ $(1\le R\le {10}^9)$ metres (inclusive) of a holographic emitter at all times.

Fortunately, there's a holographic emitter installed right at the entrance to the mess hall, and there are $N$ $(0\le N\le 200000)$ other emitters located at various points along the hallway. The $i^{th}$ of these emitters is $E_i$ $(1\le E_i<M)$ metres away from the mess hall (and thus, $M-E_i$ metres away from the bridge). No two emitters are in the same location.

The existing set of $N+1$ holographic emitters may not provide enough unbroken coverage for the EHC to be able to successfully walk from the mess hall to the bridge. If that's the case, some more emitters may need to be installed along the hallway, at any chosen locations.

Le Ferge is very, very hungry, and only the EHC is qualified enough to feed him! Given that time is of the essence, what's the minimum number of additional holographic emitters which must be installed in order for every point in the hallway to be at most $R$ metres away from at least one emitter?

In test cases worth $8/20$ of the points, $N\le 2000$ and $M\le 2000$.
In test cases worth another $8/20$ of the points, $N\le 2000$.

Input Specification

The first line of input consists of three space-separated integers $N$, $M$, and $R$.
$N$ lines follow, with the $i^{th}$ of these lines consisting of a single integer $E_i$ (for $i=1\dots N$).

Output Specification

Output a single integer - the minimum number of additional emitters required.

Sample Input

2 100 15
85
61

Sample Output

2

Sample Explanation

One possibility is to place two holographic emitters $30$ metres and $40$ metres away from the mess hall. If only the first of these emitters is added, then the EHC won't be able to traverse the section of the hallway between $45$ and $46$ metres from the mess hall (exclusive).