I. K-gap Subsequence
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

A subsequence of a given sequence of integers is a subset of the values in the sequence in the same order. A $$$k$$$-gap subsequence of a sequence of integers is a subsequence such that consecutive elements in the subsequence differ by at least $$$k$$$. For example, the sequence

3, 12, 8, 4, 2, 5, 1, 9, 8, 6, 5, 1, 7

has a $$$4$$$-gap subsequence of $$$3, 12, 8, 4, 9, 5, 1$$$ and $$$7$$$ (highlighted in bold above) since

$$$|3 - 12|$$$, $$$|12 - 8|$$$, $$$|8 - 4|$$$, $$$|4 - 9|$$$, $$$|9 - 5|$$$, $$$|5 - 1|$$$ and $$$|1 - 7|$$$ are all $$$4$$$ or greater.

Given a sequence and a value of $$$k$$$, determine the length of the longest $$$k$$$-gap subsequence.

Input

The first input line contains two space separated integers: $$$n$$$ $$$(1 ≤ n ≤ 300,000)$$$, indicating the length of the sequence, and $$$k$$$ $$$(1 ≤ k ≤ 10^9)$$$, indicating the value of $$$k$$$ for the input case. The following input line contains n space separated integers. The $$$i^{th}$$$ of these integers is $$$a_i$$$ $$$(1 ≤ a_i ≤ 10^9)$$$, the $$$i^{th}$$$ value of the input sequence.

Output

Print the length of the longest $$$k$$$-gap subsequence of the input sequence.

Examples
Input
10 2
1 2 3 2 1 3 1 3 5 6
Output
7
Input
5 12
3 7 14 20 32
Output
3
Input
13 4
3 12 8 4 2 5 1 9 8 6 5 1 7
Output
8