← 返回题目列表

AtCoder · awc0065_e

E. 温度稳定期

中文机器翻译题面 查看原题

分数: 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