Minimum Towers for Animal Observation

You are given n positions on a one-dimensional number line representing the locations of animals in a sanctuary. You need to place observation towers that can cover a range of r units to either side from the tower's position (i.e. a tower placed at position x covers the interval \( [x - r,\ x + r] \)).

Your goal is to minimize the number of towers required such that all animals are covered by at least one tower. The positions of the animals are given in sorted order.

Input Format: The first line contains two integers n and r. The second line contains n space-separated integers representing the positions of the animals.

Output Format: Output a single integer, the minimum number of towers required to cover all animals.

The problem can be formally described with the following theorem: Given positions \( p_1, p_2, \dots, p_n \) and a range \( r \), find the minimum number of intervals of length \( 2r \) (centered at some chosen point) needed to cover all points \( p_i \). The optimal greedy strategy is to choose the rightmost position that still covers the leftmost uncovered animal, place a tower, and then skip all positions covered by this tower.

inputFormat

The input is read from standard input. It consists of two lines:

• The first line contains two integers \( n \) and \( r \), where \( n \) (\( 1 \leq n \leq 10^5 \)) is the number of positions, and \( r \) (\( 0 \leq r \leq 10^9 \)) is the range of coverage of each tower.
• The second line contains \( n \) space-separated integers representing the positions of the animals in non-decreasing order.

outputFormat

The output should be written to standard output and consists of a single integer: the minimum number of towers required to cover all the animals.

## sample

6 2
1 2 3 5 7 8

2

</p>