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.

제한

힌트