Maximal Light Removal Under Safety Distance Constraint

Given \(n\) lights positioned at distinct coordinates \(p_i\) on a line and a safe distance \(dist\), you are allowed to turn off some of these lights while ensuring that the tunnel remains well lit. The leftmost and rightmost lights (i.e. the ones closest to and farthest from the tunnel entrance) must always remain turned on.

For any light \(i\) with \(1 < i < n\), it can be turned off if when it is switched off, the distance between its two neighboring turned on lights is not more than \(dist\). In other words, if the positions of two adjacent retained lights (say \(p_{\text{left}}\) and \(p_{\text{right}}\)) satisfy \[ p_{\text{right}} - p_{\text{left}} \le dist, \] then all lights between them can be turned off.

Your task is to determine the maximum number of lights that can be turned off while still ensuring that the gap between any two consecutive turned on lights is at most \(dist\). Formally, you must choose a subsequence from the sorted array of positions that includes the first and last lights and minimizes the number of lights left on (so that the gap between any two consecutive lights in the subsequence does not exceed \(dist\)). The answer is then \(n\) minus the number of lights in this subsequence.

Note: It is guaranteed that there is at least one valid way to keep the tunnel sufficiently lit.

inputFormat

The first line contains two integers \(n\) and \(dist\) \(\,(2 \le n \le 10^5,\, 1 \le dist \le 10^9)\.

The second line contains \(n\) distinct integers \(p_i\) \(\,(0 \le p_i \le 10^9)\ representing the positions of the lights.

outputFormat

Output a single integer representing the maximum number of lights that can be turned off while ensuring the adjacent turned on lights have a distance of at most \(dist\).

sample

5 10
1 3 8 10 14

2