Score: $525$ points

问题描述

你给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$。

找出 $A$ 中满足任意两个相邻项之间绝对差值不大于 $D$ 的最长子序列的长度。

序列 $A$ 的子序列是指通过从 $A$ 中删除零个或多个元素，并保持其余元素原有的相对顺序排列而得到的序列。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

You are given a sequence $A = (A_1, A_2, \ldots, A_N)$ of length $N$.

Find the maximum length of a subsequence of $A$ such that the absolute difference between any two adjacent terms is at most $D$.

A subsequence of a sequence $A$ is a sequence that can be obtained by deleting zero or more elements from $A$ and arranging the remaining elements in their original order.

Constraints

• $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$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$

$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

4 2
3 5 1 2

Sample Output 1

3

The subsequence $(3, 1, 2)$ of $A$ has absolute differences of at most $2$ between adjacent terms.

Sample Input 2

5 10
10 20 100 110 120

Sample Output 2

3

Sample Input 3

11 7
21 10 3 19 28 12 11 3 3 15 16

Sample Output 3

6

update @ 2024/3/10 01:31:40