/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は山岳写真家です。東西に一直線に並んだ N 本の山の峰があり、西から i 番目の峰の標高は H_i です。
高橋君は、区間 [l, r]（1 \leq l \leq r \leq N）に含まれる峰を写真に収めたいと考えています。ここで区間 [l, r] とは、西から l 番目、l+1 番目、\ldots、r 番目の峰からなる連続した峰の並びを指します。
美しい写真を撮るためには、峰の並びが 山型 である必要があります。
区間 [l, r] の峰の並びが 山型 であるとは、ある整数 k（l \leq k \leq r）が存在して、
H_l < H_{l+1} < \cdots < H_k > H_{k+1} > \cdots > H_r
が成り立つことを言います。すなわち、l から k までは標高が狭義単調増加し、k から r までは標高が狭義単調減少します。特に、l = r の場合（峰が 1 つだけ）も山型です。また、k = l の場合は全体が狭義単調減少、k = r の場合は全体が狭義単調増加となりますが、これらも山型に含まれます。
（補足：山型の定義では狭義の不等号を用いているため、隣接する峰の標高が等しい箇所（H_i = H_{i+1}）を含む区間は山型にはなりません。）
さらに、高橋君はダイナミックな写真を撮りたいので、区間内の標高の最大値と最小値の差、すなわち
\max(H_l, H_{l+1}, \ldots, H_r) - \min(H_l, H_{l+1}, \ldots, H_r)
が K 以上である山型の区間のみを 撮影候補 とします。
撮影候補の区間が存在する場合、その中で区間に含まれる峰の数 r - l + 1 の最大値を求めてください。撮影候補が 1 つも存在しない場合は 0 を出力してください。
制約
- 1 \leq N \leq 10^6
- 1 \leq K \leq 10^9
- 1 \leq H_i \leq 10^9
- H_i は互いに異なるとは限らない
- 入力はすべて整数である
入力
N K H_1 H_2 \ldots H_N
- 1 行目には、峰の数を表す整数 N と、標高差の下限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、西から i 番目の峰の標高を表す整数 H_i が N 個、スペース区切りで与えられる。
出力
撮影候補の区間に含まれる峰の数の最大値を 1 行で出力せよ。撮影候補が存在しない場合は 0 を出力せよ。
入力例 1
7 4 1 3 5 4 2 6 1
出力例 1
5
入力例 2
5 10 1 2 3 4 5
出力例 2
0
入力例 3
15 20 10 15 30 25 20 20 21 22 19 18 40 35 30 28 50
出力例 3
5
入力例 4
50 100 500 480 460 470 520 610 700 650 600 550 550 560 570 580 590 300 310 320 330 340 330 320 310 305 1000 900 800 700 600 500 400 410 420 430 440 450 460 470 480 490 490 100 200 300 400 350 250 150 50 25
出力例 4
9
入力例 5
1 1000000000 1000000000
出力例 5
0
Score : 366 pts
Problem Statement
Takahashi is a mountain photographer. There are N mountain peaks lined up in a straight line from west to east, and the elevation of the i-th peak from the west is H_i.
Takahashi wants to take a photo of the peaks contained in an interval [l, r] (1 \leq l \leq r \leq N). Here, the interval [l, r] refers to the contiguous sequence of peaks consisting of the l-th, (l+1)-th, \ldots, r-th peaks from the west.
To take a beautiful photo, the sequence of peaks must be mountain-shaped.
An interval [l, r] of peaks is mountain-shaped if there exists an integer k (l \leq k \leq r) such that:
H_l < H_{l+1} < \cdots < H_k > H_{k+1} > \cdots > H_r
That is, the elevation strictly increases from l to k, and strictly decreases from k to r. In particular, if l = r (only one peak), it is also mountain-shaped. If k = l, the entire sequence is strictly decreasing, and if k = r, the entire sequence is strictly increasing; these cases are also considered mountain-shaped.
(Note: Because the definition of mountain-shaped uses strict inequalities, an interval containing adjacent peaks of equal elevation (H_i = H_{i+1}) cannot be mountain-shaped.)
Furthermore, Takahashi wants to take a dynamic photo, so he only considers an interval as a shooting candidate if it is mountain-shaped and the difference between the maximum and minimum elevations in the interval, i.e.,
\max(H_l, H_{l+1}, \ldots, H_r) - \min(H_l, H_{l+1}, \ldots, H_r)
is at least K.
If there are any shooting candidate intervals, find the maximum number of peaks r - l + 1 contained in such an interval. If no shooting candidates exist, output 0.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq K \leq 10^9
- 1 \leq H_i \leq 10^9
- H_i are not necessarily distinct.
- All input values are integers.
Input
N K H_1 H_2 \ldots H_N
- The first line contains the integer N, representing the number of peaks, and the integer K, representing the lower bound of the elevation difference, separated by a space.
- The second line contains N space-separated integers, where the i-th integer represents the elevation H_i of the i-th peak from the west.
Output
Print the maximum number of peaks in a shooting candidate interval in a single line. If no shooting candidates exist, output 0.
Sample Input 1
7 4 1 3 5 4 2 6 1
Sample Output 1
5
Sample Input 2
5 10 1 2 3 4 5
Sample Output 2
0
Sample Input 3
15 20 10 15 30 25 20 20 21 22 19 18 40 35 30 28 50
Sample Output 3
5
Sample Input 4
50 100 500 480 460 470 520 610 700 650 600 550 550 560 570 580 590 300 310 320 330 340 330 320 310 305 1000 900 800 700 600 500 400 410 420 430 440 450 460 470 480 490 490 100 200 300 400 350 250 150 50 25
Sample Output 4
9
Sample Input 5
1 1000000000 1000000000
Sample Output 5
0