A Cappella Recording

Interview

Time limit1sMemory limit2048 MB

Summary

Given n pitches and a maximum allowed range d, find the fewest recordings so that each recording's max minus min pitch is at most d and every note is covered.

Level: Easy3 of 10
Topics: Sorting, Greedy
Solved: No attempts yet

Problem

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

Each note of the song has a pitch between $0$ and $10^9$ . Because the pitches vary, Geoffry records himself singing several times. In a single recording, he picks some subset of the notes and sings exactly those notes. To avoid straining his voice, the difference between the maximum pitch and the minimum pitch among the notes in one recording is limited.

Compute the minimum number of recordings needed so that every note is sung in at least one of them.

Input

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 the song and $d$ is the largest difference between the minimum and maximum pitch that Geoffry can handle.

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

Output

Output a single integer, the minimum number of recordings needed so that each note is sung in at least one of them.

Examples5

Example 1
Input
```
6 0
3
1
4
1
5
9
```
Expected output
```
5
```
Example 2
Input
```
6 1
3
1
4
1
5
9
```
Expected output
```
4
```
Example 3
Input
```
6 2
3
1
4
1
5
9
```
Expected output
```
3
```
Example 4
Input
```
6 4
3
1
4
1
5
9
```
Expected output
```
2
```
Example 5
Input
```
6 8
3
1
4
1
5
9
```
Expected output
```
1
```