Minimum Additional Sensors

You are given a one-dimensional segment from 0 to n. Along this segment, some sensors are already installed at specific positions, and each sensor has a range of coverage. A sensor installed at position p covers the interval \(\max(0, p-d)\) to \(\min(n, p+d)\) (inclusive). The goal is to determine the minimum number of additional sensors required so that the entire region from 0 to n is covered by at least one sensor.

If no sensors are installed, you should compute how many sensors are needed to cover the segment entirely. When sensors do exist, their coverage intervals might overlap. In that case, merge overlapping intervals and then compute the extra sensors required for any uncovered gaps.

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input is read from standard input (stdin) and consists of:

1. A single line containing three space-separated integers \(n\), \(d\) and \(m\), where \(n\) is the end point of the interval \([0, n]\), \(d\) is the sensor range, and \(m\) is the number of existing sensors.
2. If \(m > 0\), the next line contains \(m\) space-separated integers representing the positions of the existing sensors. If \(m = 0\), there is no second line.

Constraints: You can assume that \(0 \leq m \leq n+1\) and the sensor positions are within the range \([0, n]\).

outputFormat

Output a single integer to standard output (stdout) representing the minimum number of additional sensors required to cover the entire interval \([0, n]\).

## sample

10 2 0

2

</p>