E - 気温の安定した期間 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は気象データの分析を行っています。ある地域で N 日間にわたって毎日の最高気温が記録されており、i 日目 (1 \leq i \leq N) の最高気温は H_i ℃です。

高橋君は、この N 日間の記録の中から 連続する K 日以上 の期間であって、気温が 安定している ものを探しています。

ここで、連続する期間（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
  • 1 行目には、記録の日数を表す整数 N、期間に必要な最小日数を表す整数 K、許容される気温差（℃）を表す整数 D が、スペース区切りで与えられる。
  • 2 行目には、各日の最高気温（℃）を表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。

出力

気温が安定しており、かつ日数が K 以上であるような連続する期間が存在する場合は、その最大日数を 1 行で出力せよ。存在しない場合は -1 を 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

Score : 466 pts

Problem Statement

Takahashi is analyzing weather data. The daily maximum temperatures have been recorded over N days in a certain region, and the maximum temperature on day i (1 \leq i \leq N) is H_i ℃.

Takahashi is looking for a period of at least K consecutive days within these N days of records where the temperature is stable.

Here, the temperature in a consecutive period (from day l to day r, where 1 \leq l \leq r \leq N) is said to be "stable" if the difference between the maximum value and the minimum value among H_l, H_{l+1}, \ldots, H_r is at most D.

Among all consecutive periods where the temperature is stable and the number of days (r - l + 1) is at least K, find the maximum number of days. If no such period exists, output -1.

Constraints

  • 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)
  • All input values are integers

Input

N K D
H_1 H_2 \ldots H_N
  • The first line contains an integer N representing the number of recorded days, an integer K representing the minimum number of days required for a period, and an integer D representing the allowable temperature difference (℃), separated by spaces.
  • The second line contains integers H_1, H_2, \ldots, H_N representing the maximum temperature (℃) on each day, separated by spaces.

Output

If there exists a consecutive period where the temperature is stable and the number of days is at least K, output the maximum number of days in one line. If no such period exists, output -1 in one line.

Sample Input 1

7 3 2
10 11 10 12 15 14 13

Sample Output 1

4

Sample Input 2

5 3 1
1 3 1 3 1

Sample Output 2

-1

Sample Input 3

15 4 5
3 5 7 4 6 8 20 22 25 21 23 24 22 21 30

Sample Output 3

8

Sample Input 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

Sample Output 4

10

Sample Input 5

1 1 0
42

Sample Output 5

1