平滑子序列

题目描述

给定长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。

求 $A$ 的满足「任意两个相邻项之差的绝对值不超过 $D$」的子序列的最大长度。

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

输入格式

输入按以下格式从标准输入给出：

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

输出格式

输出答案。

样例

4 2
3 5 1 2

3

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

5 10
10 20 100 110 120

3

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

6

数据范围

• $1 \le N \le 5 \times 10^5$
• $0 \le D \le 5 \times 10^5$
• $1 \le A_i \le 5 \times 10^5$
• 所有输入值均为整数