分数: 433 分
问题陈述
高桥是一家美术馆的馆长。博物馆有 N 作为展览候选作品,编号自 1 to N。的评价分数 i第一项工作是 H_i.
高桥已决定选择 1 或更多这些作品可供展出。同一作品不得多次入选。选中的作品按编号升序排列显示(排列顺序不能随意更改)。
为了保持展览的统一感,作品的排列顺序必须满足以下条件:
- 让 k (k \geq 1) 为所选作品的数量,令其为 a_1, a_2, \ldots, a_k (a_1 < a_2 < \cdots < a_k)按其编号升序排列。那么,对于所有 1 \leq j \leq k-1, |H_{a_j} - H_{a_{j+1}}| \leq D 必须保留。
也就是说,在按编号顺序排列的参展作品序列中,每两个相邻作品的评价分数的绝对差值不得超过 D。当仅选择一件作品时,不存在相邻对,因此自动满足此条件。
高桥希望展出尽可能多的作品。求在满足上述条件的情况下,最多可以选择多少件作品。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq D \leq 10^9
- 1 \leq H_i \leq 10^9
- 所有输入值均为整数。
输入
N D H_1 H_2 \ldots H_N
- 第一行包含一个整数 N 代表作品数量和一个整数 D 代表相邻作品之间允许的评价分数绝对差值的上限(含),以空格分隔。
- 第二行包含整数 H_1, H_2, \ldots, H_N 代表每件作品的评价分数,以空格分隔。
输出
在一行中输出满足条件时可以选择的最大作品数。
示例输入 1
5 3 4 1 5 8 3
示例输出 1
3
示例输入 2
5 0 3 1 3 3 2
示例输出 2
3
示例输入 3
10 5 10 3 8 12 7 15 9 6 11 2
示例输出 3
7
示例输入 4
20 10 50 45 55 40 35 30 25 20 28 33 38 43 48 53 58 63 68 60 55 50
示例输出 4
19
示例输入 5
1 0 1000000000
示例输出 5
1