版权声明

本题版权归 Long Long OJ 所有。

题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$。寻找满足以下条件的 $a$ 的子序列 $b$ 的最长长度：

• $b$ 中最大值与 $b$ 中最小值的差小于等于给定的整数 $k$。

提示：序列 $a$ 的子序列指删除 $a$ 中若干个元素（可能是 $0$ 个） 后重新把剩下的元素按原来的顺序排列得到的序列。一个序列有多个子序列。

输入格式

• 第一行：两个正整数 $n,k$。
• 第二行：$n$ 个整数，第 $i$ 个是 $a_i$。

输出格式

一行一个正整数，表示答案。

样例

5 12
60 10 33 46 21

2

选出的最长子序列是 $[10,21]$ 或 $[21,33]$，长度都为 $2$。

5 100
18 -14 -114 19 -81

4

选出的最长子序列是 $[18,-14,19,-81]$，长度为 $4$。此外，$a_i$ 可能是负数。

数据范围

• 对于 $10\%$ 的数据，$1\leq n,a_i \leq 10$；
• 对于 $20\%$ 的数据，$1\leq n\leq 20$；
• 对于 $55\%$ 的数据，$1\leq n\leq 5000$；
• 对于另外 $5\%$ 的数据，$1\leq a_i$；
• 对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$-10^9 \leq a_i \leq 10^9$。