← 返回题目列表

AtCoder · abl_d

D. 平坦子序列

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

分数: 400 点

问题陈述

给你一个序列 A_1, A_2, ..., A_N 和一个整数 K.

打印序列的最大可能长度 B 满足以下条件:

  • B 是(不一定是连续的)子序列 A.
  • 对于每对相邻元素 B,元素的绝对差最多为 K.

约束

  • 1 \leq N \leq 300,000
  • 0 \leq A_i \leq 300,000
  • 0 \leq K \leq 300,000
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_1
A_2
:
A_N

输出

打印答案。


示例输入 1

10 3
1
5
4
3
8
6
9
7
2
4

示例输出 1

7

例如, B = (1, 4, 3, 6, 9, 7, 4) 满足条件。

  • 这是一个子序列 A = (1, 5, 4, 3, 8, 6, 9, 7, 2, 4).
  • 两个相邻元素之间的所有绝对差(|1-4|, |4-3|, |3-6|, |6-9|, |9-7|, |7-4|) 最多 K = 3.