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