分数: 466 分
问题陈述
Takahashi 正在分析天气数据。每日最高气温记录超过 N 某地区的天数以及当日最高气温 i (1 \leq i \leq N) is H_i ℃.
高桥正在寻找一段时间 至少 K 连续天 其中 N 温度记录天数 稳定.
这里,连续一段时间(从一天开始)的温度 l 到今天 r,其中 1 \leq l \leq r \leq N)如果最大值和最小值之间的差值被认为是“稳定的” H_l, H_{l+1}, \ldots, H_r 最多是 D.
在所有连续温度稳定的时期和天数(r - l + 1) 至少 K,找到 最大 天数。如果不存在这样的时期,则输出 -1.
约束
- 1 \leq N \leq 5 \times 10^5
- 1 \leq K \leq N
- 0 \leq D \leq 10^9
- -10^9 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 所有输入值均为整数
输入
N K D H_1 H_2 \ldots H_N
- 第一行包含一个整数 N 代表记录天数,整数 K 表示一个周期所需的最小天数,整数 D 代表允许温差(℃),以空格分隔。
- 第二行包含整数 H_1, H_2, \ldots, H_N 代表每天的最高气温(℃),以空格分隔。
输出
如果存在连续一段时间气温稳定且天数至少为 K,一行输出最大天数。如果不存在这样的时期,则输出 -1 一行。
示例输入 1
7 3 2 10 11 10 12 15 14 13
示例输出 1
4
示例输入 2
5 3 1 1 3 1 3 1
示例输出 2
-1
示例输入 3
15 4 5 3 5 7 4 6 8 20 22 25 21 23 24 22 21 30
示例输出 3
8
示例输入 4
30 5 3 1 2 3 4 100 10 11 12 13 12 11 10 11 12 13 200 50 51 52 53 51 50 52 53 51 50 300 400 500 600
示例输出 4
10
示例输入 5
1 1 0 42
示例输出 5
1