Your street has ~n~ houses, conveniently numbered from ~1~ to ~n~. Out of these ~n~ houses, ~k~ of them have security 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 \le n \le 100\,000)~, ~k~ ~(0 \le k \le n)~ , and ~r~ ~(2 \le r \le 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