103394: [Atcoder]ABC339 E - Smooth Subsequence

Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$.

Find the maximum length of a subsequence of $A$ such that the absolute difference between any two adjacent terms is at most $D$.

A subsequence of a sequence $A$ is a sequence that can be obtained by deleting zero or more elements from $A$ and arranging the remaining elements in their original order.

Constraints

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq D \leq 5 \times 10^5$
• $1 \leq A_i \leq 5 \times 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

4 2
3 5 1 2

Sample Output 1

3

The subsequence $(3, 1, 2)$ of $A$ has absolute differences of at most $2$ between adjacent terms.

Sample Input 2

5 10
10 20 100 110 120

Sample Output 2

3

Sample Input 3

11 7
21 10 3 19 28 12 11 3 3 15 16

Sample Output 3

6

问题描述

给你一个长度为 N 的序列 A = (A_1, A_2, \ldots, A_N)。

找出 A 的一个子序列，使得这个子序列中任意两个相邻项的绝对差不超过 D。

一个序列 A 的子序列是指从 A 中删除零个或多个元素，并将剩余元素按原顺序排列后得到的序列。

约束条件

• $1 \leq N \leq 5 \times 10^5$
• $0 \leq D \leq 5 \times 10^5$
• $1 \leq A_i \leq 5 \times 10^5$
• 所有输入值都是整数。

输入

输入通过标准输入给出，格式如下：

$N$ $D$
$A_1$ $A_2$ $\ldots$ $A_N$

输出

输出答案。

样例输入 1

4 2
3 5 1 2

样例输出 1

3

A 的子序列 $(3, 1, 2)$ 中，相邻项的绝对差不超过 2。

样例输入 2

5 10
10 20 100 110 120

样例输出 2

3

样例输入 3

11 7
21 10 3 19 28 12 11 3 3 15 16

样例输出 3

6