13978번 - Cameras 다국어

Your street has n houses, conveniently numbered from 1 to n. Out of these n houses, k of them have security cameras installed. Mindful of gaps in coverage, the Neighborhood Watch would like to ensure that every set of r consecutive houses has at least two different houses with cameras. What is the minimum number of additional cameras necessary to achieve this?

The first line of input contains three integers, n (2 ≤ n ≤ 100,000), k (0 ≤ k ≤ n), and r (2 ≤ r ≤ n).

The next k lines of input contain the distinct locations of the existing cameras.

Print, on a single line, a single integer indicating the minimum number of cameras that need to be added.