分数: 525 点
问题陈述
给你一个序列 A = (A_1, A_2, \ldots, A_N) 长度 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
子序列 (3, 1, 2) of A 的绝对差异最多为 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