题目背景

警告：滥用本题评测将被封号！

题目描述

有一个长度为 $N$ 的序列 $A_i$，定义函数 $f(m,p_1,p_2,\cdots,p_m)$ 的值为满足：

的 $p_i$ 的个数，当 $i=1$ 时，我们假设上面这个不等式是恒成立的。

给定一个整数 $D$，求一个序列 $p_i$ 满足：

• $1 \le m \le N$；
• $p_m=N$；
• $p_i<p_{i+1}$；
• 如果 $m \ge 2$，那么有 $p_{j+1}-p_j \le D$；
• $f(m,p_1,p_2,\dots,p_m)$ 的值最大。

求 $f$ 函数的最大值。

输入格式

第一行两个整数 $N,D$，意义如题面所述。

第二行 $N$ 个整数 $A_i$ 代表给定的序列。

输出格式

一行一个整数代表 $f$ 函数的最大值。

7 1
100 600 600 200 300 500 500

3

6 6
100 500 200 400 600 300

4

11 2
1 4 4 2 2 4 9 5 7 0 3

4

提示

样例 1 解释

一共有 $7$ 种可能的情况：

• $p_i=\{1,2,3,4,5,6,7\}$，$f(7,1,2,3,4,5,6,7)=2$；
• $p_i=\{2,3,4,5,6,7\}$，$f(6,2,3,4,5,6,7)=1$；
• $p_i=\{3,4,5,6,7\}$，$f(5,3,4,5,6,7)=1$；
• $p_i=\{4,5,6,7\}$，$f(4,4,5,6,7)=3$；
• $p_i=\{5,6,7\}$，$f(3,5,6,7)=2$；
• $p_i=\{6,7\}$，$f(2,6,7)=1$；
• $p_i=\{7\}$，$f(1,7)=1$。

最大值为 $3$。

样例 2 解释

最优的 $p_i=\{1,3,4,5,6\}$，对应的 $A_i=\{100,200,400,600,300\}$，$f$ 函数值为 $4$。

样例 3 解释

最优的方式有多种，其中一种是 $p_i=\{1,3,5,6,8,9,11\}$，对应的 $A_i=\{ 1, 4, 2, 4, 5, 7, 3\}$，$f$ 函数值为 $4$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（14 pts）：$N \le 20$；
• Subtask 2（14 pts）：$N \le 400$；
• Subtask 3（20 pts）：$N \le 7000$；
• Subtask 4（12 pts）：$D=1$；
• Subtask 5（5 pts）：$D=N$；
• Subtask 6（35 pts）：无特殊限制。

对于 $100\%$ 的数据：

• $1 \le N \le 3 \times 10^5$；
• $1 \le D \le N$；
• $0 \le A_i \le 10^9$。

说明

翻译自 JOI 2020 / 2021 Open Contest B Financial Report。