← 返回题目列表

AtCoder · abc339_e

H. 平滑子序列

中文机器翻译题面 查看原题

分数: 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