题目描述

译自 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$。

输出格式

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

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\le N\le 3\times 10^5$
• $1\le D\le N$
• $0\le A_i\le 10^9\ (1\le i\le N)$

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