A Cappella Recording

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

요약

n개의 음높이와 허용 차이 d가 주어질 때, 각 묶음의 최대 최소 차이가 d 이하가 되도록 모든 음을 덮는 최소 묶음 수를 구한다.

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

문제

Geoffry is preparing an a cappella composition where he sings the entire song by himself.

Each note of the song has a pitch between $0$ and $10^9$ . Because of the varying pitches in the song, Geoffry will record himself singing multiple times. In a single recording, he will pick some subset of the notes to sing and he will sing exactly those notes. To avoid straining his voice too much, within a single recording, there is a limit to the difference between the maximum pitch and the minimum pitch among the notes he sings.

Compute the minimum number of times that Geoffry can record himself singing the song and each note is sung in at least one of the recordings.

입력

The first line contains two integers $n$ and $d$ ( $1 \le n \le 10^5, 0 \le d \le 10^9$ ), where $n$ is the number of notes in Geoffry's song, and $d$ is the largest difference between the minimum pitch and the maximum pitch that Geoffry can handle.

Each of the next $n$ lines contains a single integer $p$ ( $0 \le p \le 10^9$ ). These are the pitches of the notes in Geoffry's song, in the order that they are to be sung.

출력

Output a single integer, which is the minimum number of times that Geoffry can record himself singing the song and each note is sung in at least one of the recordings.

예제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
```