오리와 박수치는 춘배

면접 대비

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

요약

오리가 꽥꽥거린 시각 N개와 간격 K가 주어질 때, 모든 구간 [X_i, X_i+K]에 박수가 최소 한 번 들어가도록 하는 최소 박수 횟수를 구합니다.

문제

춘배는 오리를 보러 왔다. 오리는 춘배가 있는 동안 총 $N$ 번 "꽥꽥" 소리를 낸다. 오리의 소리를 듣고 감동받은 춘배는 오리에게 박수를 쳐준다.

오리가 $X_i$ 초에 "꽥꽥" 소리를 낸다면, 소리를 들은 춘배는 $X_i$ 초 이상 $X_i+K$ 초 이하에 한 번 이상 박수를 쳐야 한다.

만약 오리가 소리를 낸 $X_i$ 초부터 $X_i+K$ 초 사이에 한 번도 박수를 쳐주지 않는다면, 실망한 오리는 집으로 가버린다. 예를 들어 $K=2$ , $X_i=5$ 라면 $5$ 초, $6$ 초, $7$ 초 중 최소 한 번은 박수를 쳐야 한다.

<박수를 치는 춘배의 모습>

오리가 집으로 가지 않도록 춘배가 박수를 쳐줄 때 박수를 최소 몇 번 쳐야 하는지 구해보자.

첫째 줄에 오리가 "꽥꽥" 소리를 내는 횟수 $N$ 과 정수 $K$ 가 공백으로 구분되어 주어진다. ( $1 \le N \le 100\,000$ , $0 \le K \le 10^6$ )

둘째 줄에 오리가 "꽥꽥" 소리를 내는 시각 $X_1, X_2, \ldots, X_N$ 이 공백으로 구분되어 주어진다. $X_i$ 는 서로 다르며 오름차순으로 주어진다. ( $1 \le X_i \le 10^6$ )

오리가 집으로 가지 않도록 춘배가 박수를 쳐줄 때 박수를 최소 몇 번 쳐야 하는지 출력한다.