K-gap Subsequence

Interview

Time limit1sMemory limit1024 MB

Summary

Find the length of the longest subsequence in which every pair of consecutive elements differs by at least k.

Level: Medium6 of 10
Topics: Dynamic programming, Segment tree, Sorting
Solved: No attempts yet

Problem

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 line contains two space separated integers n and k. Here n ( $1 \le n \le 300000$ ) is the length of the sequence, and k ( $1 \le k \le 10^9$ ) is the value of k for this input case.

The second line contains n space separated integers. The i-th of these integers is $a_i$ ( $1 \le a_i \le 10^9$ ), the i-th value of the input sequence.

Output

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

Examples3

Example 1
Input
```
10 2
1 2 3 2 1 3 1 3 5 6
```
Expected output
```
7
```
Example 2
Input
```
5 12
3 7 14 20 32
```
Expected output
```
3
```
Example 3
Input
```
13 4
3 12 8 4 2 5 1 9 8 6 5 1 7
```
Expected output
```
8
```