/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は、山岳ガイドとして登山道の調査を行っています。
調査対象の登山道には N 個の地点が順番に並んでおり、各地点には標高が記録されています。i 番目の地点の標高は A_i メートルです。
高橋君は「安定した登山区間」を見つけたいと考えています。安定した登山区間とは、連続する 1 個以上の地点からなる区間であって、その区間内で隣り合うどの 2 地点についても標高差が K メートル以下であるものを指します。
具体的には、地点 i から地点 j（i \leq j）までが安定した登山区間であるとは、すべての i \leq k < j について |A_k - A_{k+1}| \leq K が成り立つことを意味します。特に、1 個の地点のみからなる区間（i = j の場合）は常に安定した登山区間です。
隣り合う地点間の標高差が K メートルを超える箇所は、急な崖や段差があり安全に通行できないため、そのような箇所をまたぐ区間は安定した登山区間とはみなされません。
高橋君は、最も長い安定した登山区間の長さを求めたいです。ここで、区間の長さとは、その区間に含まれる地点の個数のことです。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、地点の総数を表す整数 N と、隣り合う地点間の標高差の許容上限を表す整数 K が、スペース区切りで与えられる。
- 2 行目には、各地点の標高を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
最も長い安定した登山区間の長さを 1 行で出力せよ。
入力例 1
6 3 10 12 15 20 18 19
出力例 1
3
入力例 2
10 5 100 103 108 115 110 112 114 116 130 125
出力例 2
5
入力例 3
15 10 50 55 60 58 100 95 90 85 82 80 79 150 145 140 138
出力例 3
7
Score : 300 pts
Problem Statement
Takahashi is conducting a survey of mountain trails as a mountain guide.
The trail being surveyed consists of N points arranged in order, each with a recorded elevation. The elevation of the i-th point is A_i meters.
Takahashi wants to find "stable hiking sections." A stable hiking section is a contiguous section consisting of 1 or more points such that for every pair of adjacent points within the section, the elevation difference is at most K meters.
Specifically, the section from point i to point j (i \leq j) is a stable hiking section if and only if |A_k - A_{k+1}| \leq K holds for all i \leq k < j. In particular, a section consisting of only 1 point (when i = j) is always a stable hiking section.
Locations where the elevation difference between adjacent points exceeds K meters have steep cliffs or steps that cannot be safely traversed, so sections that span such locations are not considered stable hiking sections.
Takahashi wants to find the length of the longest stable hiking section. Here, the length of a section refers to the number of points contained in that section.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- 0 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the total number of points and an integer K representing the maximum allowable elevation difference between adjacent points, separated by a space.
- The second line contains integers A_1, A_2, \ldots, A_N representing the elevation of each point, separated by spaces.
Output
Print the length of the longest stable hiking section in one line.
Sample Input 1
6 3 10 12 15 20 18 19
Sample Output 1
3
Sample Input 2
10 5 100 103 108 115 110 112 114 116 130 125
Sample Output 2
5
Sample Input 3
15 10 50 55 60 58 100 95 90 85 82 80 79 150 145 140 138
Sample Output 3
7