财务报告 - 题目

JOI 超市拥有 $N$ 天的经营历史。在 JOI 超市开业后的第 $i$ 天（$1 \le i \le N$），其销售额为 $A_i$ 日元。

Bitaro 是 JOI 超市的店长，他将制作一份财务报告演示文稿。为了进行演示，他将选择其中的若干天，并按时间顺序展示所选日期的销售额柱状图。他将解释这些日期的销售额是如何变化的。为了使演示文稿更具感染力，他计划选择合适的日期，以使演示文稿呈现出更好的效果。

如果 Bitaro 选择 $m$ 天的销售额数据（$1 \le m \le N$），且选择的是开业后的第 $p_1, p_2, \dots, p_m$ 天（$1 \le p_1 < p_2 < \dots < p_m \le N$），则柱状图的“印象分”计算如下：

印象分等于所选日期中创下销售额新高的次数。换句话说，印象分等于满足以下条件的索引 $j$（$1 \le j \le m$）的数量：$j = 1$ 或者 $\max\{A_{p_1}, A_{p_2}, \dots, A_{p_{j-1}}\} < A_{p_j}$。

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$ $A_1 \ \dots \ A_N$

输出一行到标准输出。输出应包含演示文稿柱状图的最大印象分。

7 1
100 600 600 200 300 500 500

6 6
100 500 200 400 600 300

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

QOJ.ac