Repairing Pipe Leaks

Interview

Time limit2sMemory limit128 MB

Summary

Given leak positions and a fixed tape length, compute the minimum number of length-L tapes needed so each leak is covered with at least 0.5 margin on both sides.

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

Problem

A water pipe is leaking at several points. Each leak is given as an integer distance from the left end of the pipe.

You may use any number of tapes, each of length L. To seal a leak, the tape must cover at least 0.5 units to the left and at least 0.5 units to the right of that leak. Tapes cannot be cut, but they may overlap.

Given the leak positions and the tape length L, find the minimum number of tapes needed to seal all leaks.

Input

The first line contains the number of leaks N and the tape length L. The second line contains N leak positions.

N and L are integers between 1 and 1,000, inclusive. Each position is an integer between 1 and 1,000, inclusive.

Output

Print the minimum number of tapes needed.

Examples3

Example 1
Input
```
4 2
1 2 100 101
```
Expected output
```
2
```
Example 2
Input
```
4 3
1 2 3 4
```
Expected output
```
2
```
Example 3
Input
```
3 1
3 2 1
```
Expected output
```
3
```