题目描述

译自 JOI Open 2021 T2 「決算報告 / Financial Report」

JOI 超市是一家有着 $N$ 天历史的超市。在 JOI 超市开张后，第 $i\ (1\le i\le N)$ 天的销售额是 $A_i$ 日元。

Bitaro 是 JOI 超市的经理，他负责做财务报告。在报告中，他会选择一些天，用柱形图按时间顺序展示这些天的销售额。他会解释这些天销售额是如何变化的。为了使得这个报告给人留下更深的印象，他计划自己选择要展示的数据。

如果 Bitaro 选了 $m\ (1\le m\le N)$ 天的销售额数据，这 $m$ 天分别为开业后第 $p_1,p_2,\ldots ,p_m\ (1\le p_1<p_2<\ldots <p_m\le N)$ 天，那么一个柱形图的印象分按如下规则计算。

• 印象分等于在这些天中销售额创历史新高的天数。换句话说，印象分等于满足 $j=1$ 或 $\max\{A_{p_1},A_{p_2},\ldots ,A_{p_{j-1}} \}<A_{p_j}$ 的下标 $j\ (1\le j\le m)$ 的个数。

Bitaro 想要最大化印象分，但是对于某些数据的选法，这个报告可能会不太自然。因此，他决定选择满足如下条件的数据。

• Bitaro 会展示最新的销售额数据。换句话说，满足 $p_m=N$。
• 对于报告中展示的两个连续的销售额数据，两天日期最多差 $D$ 天。换句话说，如果 $m\ge 2$，对于每个 $j\ (1\le j\le m-1)$，都要满足不等式 $p_{j+1}-p_j\le D$。

给出 JOI 超市开业后的销售额数据和一个整数 $D$，计算报告中的柱形图的最大印象分。

输入格式

第一行两个整数 $N,D$。

第二行 $N$ 个整数 $A_i$。

输出格式

输出一行一个整数，表示最大印象分。

样例 1

7 1
100 600 600 200 300 500 500

3

在这组样例中，报告中可能有 $7$ 种满足条件的柱形图。

• 如果 Bitaro 用从开业起第 $1,2,3,4,5,6,7$ 天的数据，印象分是 $2$。
• 如果 Bitaro 用从开业起第 $2,3,4,5,6,7$ 天的数据，印象分是 $1$。
• 如果 Bitaro 用从开业起第 $3,4,5,6,7$ 天的数据，印象分是 $1$。
• 如果 Bitaro 用从开业起第 $4,5,6,7$ 天的数据，印象分是 $3$。
• 如果 Bitaro 用从开业起第 $5,6,7$ 天的数据，印象分是 $2$。
• 如果 Bitaro 用从开业起第 $6,7$ 天的数据，印象分是 $1$。
• 如果 Bitaro 用从开业起第 $7$ 天的数据，印象分是 $1$。

因此最大印象分是 $3$。如果你的程序输出 $3$，则你的程序被认为是正确的。

这组样例满足子任务 $1,2,3,4,6$ 的限制。

6 6
100 500 200 400 600 300

4

在这组样例中，如果 Bitaro 展示开业起第 $1,3,4,5,6$ 天的数据，印象分最大。被选的天里，销售额分别为 $100,200,400,600,300$ 日元。因为销售额创历史新高的天数为 $4$。因此输出 $4$。

这组样例满足子任务 $1,2,3,5,6$ 的限制。

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

4

在这组样例中，如果 Bitaro 展示开业起第 $1,3,5,6,8,9,11$ 天的数据，印象分最大。被选的天里，销售额分别为 $1,4,2,4,5,7,3$ 日元。因为销售额创历史新高的天数为 $4$。因此输出 $4$。注意，在这组样例输入中，有多种方式能够使得印象分为 $4$。

这组样例满足子任务 $1,2,3,6$ 的限制。

数据范围与提示

对于全部数据，满足：

• $1\le N\le 3\times 10^5$
• $1\le D\le N$
• $0\le A_i\le 10^9\ (1\le i\le N)$

详细子任务附加限制及分值如下表。