감시 카메라

면접 대비

시간 제한1초메모리 제한512 MB

요약

이미 카메라가 설치된 집들이 주어질 때, 연속한 r개 집마다 카메라가 최소 두 대 있도록 추가로 설치할 최소 개수를 구한다.

난이도: 보통10점 중 6점
유형: 그리디, 슬라이딩 윈도우, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

거리에 집 $n$ 채가 있고 $1$ 번부터 $n$ 번까지 번호가 붙어 있다. 이 가운데 $k$ 채에는 이미 감시 카메라가 설치되어 있다. 자율방범대는 감시 공백이 생기지 않도록, 연속한 집 $r$ 채로 이루어진 모든 구간에 카메라가 설치된 집이 서로 다른 두 채 이상 있게 만들려고 한다. 이 조건을 만족시키려면 카메라를 최소 몇 대 더 설치해야 하는지 구하라.

입력

첫째 줄에 정수 $n$ , $k$ , $r$ 이 주어진다 ( $2 \le n \le 100000$ , $0 \le k \le n$ , $2 \le r \le n$ ).

다음 $k$ 개 줄에는 이미 카메라가 설치된 집의 번호가 한 줄에 하나씩 주어진다. 번호는 모두 서로 다르고, 주어지는 순서는 정해져 있지 않다.

출력

추가로 설치해야 하는 카메라의 최소 개수를 한 줄에 출력한다.

예제3

예제 1
입력
```
15 5 4
2
5
7
10
13
```
예상 출력
```
3
```
예제 2
입력
```
2 0 2
```
예상 출력
```
2
```
예제 3
입력
```
12 4 5
9
2
11
4
```
예상 출력
```
1
```