Advent Street Lights

It is the Advent season! In this problem, you are given a street of length N meters (meters are numbered from 1 to N) and M street lights located at distinct positions. Each street light at position X lights up all the meters in the range \( [X-K,\; X+K] \) (inclusive). Note that a meter might be lit by several lights. However, it is possible that the entire street is not lit. Your task is to determine the minimal number of additional street lights that need to be installed (each new light can only be placed at an integer meter position between 1 and N) so that the entire street becomes lit.

Useful Note: For a street light located at \( X \), its lit range is given by the interval \( [\max(1, X-K),\; \min(N, X+K)] \).

inputFormat

The first line contains three integers: N, M and K, where N is the length of the street, M is the number of existing street lights, and K is the distance each light can cover to the left and right.
The second line contains M distinct integers representing the positions of the existing street lights.

\(1 \leq N \leq 10^9\), \(1 \leq M \leq 10^5\), and \(0 \leq K \leq N\).

outputFormat

Output a single integer — the minimal number of additional street lights needed to ensure that every meter from 1 to N is lit.

sample

10 2 2
3 8

0