题目描述

定义猫猫虫序列为对于所有 $2 \leq i \leq n$ ,都有 $|a_i-a_{i-1}| \leq k$ 的序列，其中 $|x|$ 表示 $x$ 的绝对值。

Capoo 给了你一个长度为 $n$ 的序列，你需要找出其子序列中是猫猫虫序列的最长子序列的长度。

请回忆，一个序列 $A$ 的子序列，是指通过从 $A$ 中删除零个或多个元素，但不改变其余元素的原有相对顺序，所得到的新序列。

例如，对于序列 A = {1, 3, 2, 4}：

• {1, 2, 4} 是一个子序列 (删除了 3)。
• {3, 4} 是一个子序列 (删除了 1 和 2)。
• {1, 3, 2, 4} 本身也是一个子序列 (删除了零个元素)。
• {1, 2, 3} 不是一个子序列，因为 3 和 2 的相对顺序改变了。
• {1, 4, 5} 不是一个子序列，因为包含了原序列中没有的元素 5。

请注意子序列不一定需要连续，这一点与子串的定义不同。

输入格式

输入第一行两个整数 $n$ , $k$ ,含义见题意。 $(1 \leq n \leq 5000,1 \leq k \leq 10^9)$

输入第二行 $n$ 个整数 $a_i$ ,第 $i$ 个数表示序列中的第 $i$ 个元素。 $(1 \leq a_i \leq 10^9)$

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1

7 2
5 1 3 6 8 1 6

输出 #1

4

说明与提示

对于样例 #1:

选择第 $1$ , $4$ , $5$ , $7$ 个元素组成的子序列是最长的猫猫虫子序列。