← 返回题目列表

AtCoder · awc0061_e

E. 参展作品精选

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

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