|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||512 MB||19||13||11||78.571%|
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.
15 5 4 2 5 7 10 13