감시 카메라

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

보통6그리디슬라이딩 윈도우시뮬레이션면접 대비아직 제출이 없습니다시간 제한1초메모리 제한512 MB

문제 설명

예제3

문제

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

입력

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

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

출력

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