어카펠라 녹음

면접 대비

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

요약

음높이 n개와 허용 범위 d가 주어질 때, 각 녹음의 최고 음과 최저 음의 차이가 d 이하가 되도록 모든 음을 덮는 최소 녹음 횟수를 구합니다.

난이도: 쉬움10점 중 3점
유형: 정렬, 그리디
정답자: 아직 제출이 없습니다

문제

게프리는 노래 전체를 혼자 부르는 아카펠라 곡을 준비하고 있다.

곡의 각 음에는 $0$ 이상 $10^9$ 이하의 음높이가 있다. 음높이가 다양하기 때문에 게프리는 여러 번 녹음한다. 한 번의 녹음에서는 음 중 일부를 골라 그 음들만 부른다. 목소리에 무리가 가지 않도록, 한 번의 녹음에서 부르는 음들의 최고 음높이와 최저 음높이 차이에 상한이 있다.

모든 음이 적어도 한 번의 녹음에서 불리도록 할 때, 필요한 녹음 횟수의 최솟값을 구하시오.

입력

첫째 줄에 두 정수 $n$ 과 $d$ 가 주어진다 ( $1 \le n \le 10^5$ , $0 \le d \le 10^9$ ). $n$ 은 곡의 음 개수이고, $d$ 는 게프리가 감당할 수 있는 최고 음높이와 최저 음높이 차이의 최댓값이다.

이어지는 $n$ 개의 줄에는 각각 정수 $p$ 가 하나씩 주어진다 ( $0 \le p \le 10^9$ ). 이 값들은 부르는 순서대로 주어진 음높이이다.

출력

모든 음이 적어도 한 번의 녹음에서 불리도록 할 때, 필요한 녹음 횟수의 최솟값을 한 줄에 출력한다.

예제5

예제 1
입력
```
6 0
3
1
4
1
5
9
```
예상 출력
```
5
```
예제 2
입력
```
6 1
3
1
4
1
5
9
```
예상 출력
```
4
```
예제 3
입력
```
6 2
3
1
4
1
5
9
```
예상 출력
```
3
```
예제 4
입력
```
6 4
3
1
4
1
5
9
```
예상 출력
```
2
```
예제 5
입력
```
6 8
3
1
4
1
5
9
```
예상 출력
```
1
```