409140: GYM103446 E Strange Integers

Given $$$n$$$ integers $$$A_1, A_2, \cdots, A_n$$$ and a parameter $$$k$$$, you should choose some integers $$$A_{b_1}, A_{b_2}, \cdots, A_{b_m} \, (1 \le b_1 < b_2 < \cdots < b_m \le n)$$$ so that $$$\forall 1 \le i < j \le m, |A_{b_i} - A_{b_j}| \ge k$$$. Determine the maximum number of the integers you can choose.

The first line contains two integers $$$n,k\,(1 \le n \le 10^5, 0 \le k \le 10^9)$$$, denoting the number of given integers and the given parameter.

The second line contains $$$n$$$ integers $$$A_1, A_2, \cdots, A_n \, (1 \le A_i \le 10^9)$$$, denoting the given integers.

Output one line containing one integer, denoting the maximum number of the integers you can choose.

11 2
3 1 4 1 5 9 2 6 5 3 5

4

One possible scheme is to choose $$$\{A_3 = 4, A_6 = 9, A_7 = 2, A_8 = 6\}$$$.