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

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

配点 : 466 点

問題文

高橋君は気象データの分析を行っています。手元には N 日間の気温記録があり、i 日目 (1 \leq i \leq N) の気温は A_i 度です。

高橋君は、気温が安定していた期間を調べたいと考えています。整数の組 (l, r) が 1 \leq l \leq r \leq N を満たすとき、l 日目から r 日目までの連続する r - l + 1 日間を「期間」と呼びます。期間内の気温の最大値と最小値の差が K 以下であるとき、すなわち

\max(A_l, A_{l+1}, \ldots, A_r) - \min(A_l, A_{l+1}, \ldots, A_r) \leq K

が成り立つとき、その期間は「安定している」といいます。

l = r である1日間の期間では最大値と最小値が等しく差が 0 となるため、K \geq 0 である本問の制約のもとで必ず安定しています。したがって、安定している期間は少なくとも N 個存在します。安定している期間のうち、最も長いものの日数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • -10^9 \leq A_i \leq 10^9
  • 入力はすべて整数

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、気温記録の日数 N と、安定とみなす気温差の上限 K が空白区切りで与えられる。
  • 2 行目には、各日の気温 A_1, A_2, \ldots, A_N が空白区切りで与えられる。

出力

安定している期間の最大の日数を 1 行で出力せよ。

入力例 1

7 3
20 22 21 23 19 25 24

出力例 1

4

入力例 2

10 5
15 18 12 14 16 20 19 17 22 25

出力例 2

4

入力例 3

15 10
-5 0 3 -2 5 8 2 -1 4 20 25 22 28 30 18

出力例 3

8

Score : 466 pts

Problem Statement

Takahashi is analyzing weather data. He has temperature records for N days, where the temperature on day i (1 \leq i \leq N) is A_i degrees.

Takahashi wants to find periods during which the temperature was stable. When a pair of integers (l, r) satisfies 1 \leq l \leq r \leq N, the consecutive r - l + 1 days from day l to day r are called a "period." A period is said to be "stable" when the difference between the maximum and minimum temperatures within the period is at most K, that is, when

\max(A_l, A_{l+1}, \ldots, A_r) - \min(A_l, A_{l+1}, \ldots, A_r) \leq K

holds.

For a period of 1 day where l = r, the maximum and minimum values are equal, so the difference is 0. Under the constraints of this problem where K \geq 0, such a period is always stable. Therefore, there are at least N stable periods. Find the number of days in the longest stable period.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • -10^9 \leq A_i \leq 10^9
  • All inputs are integers

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains the number of days N in the temperature record and the upper limit K of the temperature difference to be considered stable, separated by a space.
  • The second line contains the temperatures for each day A_1, A_2, \ldots, A_N, separated by spaces.

Output

Print the maximum number of days of a stable period in one line.

Sample Input 1

7 3
20 22 21 23 19 25 24

Sample Output 1

4

Sample Input 2

10 5
15 18 12 14 16 20 19 17 22 25

Sample Output 2

4

Sample Input 3

15 10
-5 0 3 -2 5 8 2 -1 4 20 25 22 28 30 18

Sample Output 3

8