/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 525 点
問題文
長さ N の数列 A = (A_1, A_2, \ldots, A_N) が与えられます。
A の部分列であって、隣接する 2 項の差の絶対値が D 以下であるようなものの長さの最大値を求めてください。
ただし、数列 A の部分列とは、A の要素を 0 個以上選んで削除し、残った要素を元の順序を保って並べた数列のことを指します。
制約
- 1 \leq N \leq 5 \times 10^5
- 0 \leq D \leq 5 \times 10^5
- 1 \leq A_i \leq 5 \times 10^5
- 入力される数値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
4 2 3 5 1 2
出力例 1
3
A の部分列 (3, 1, 2) は隣接する 2 項の差の絶対値が 2 以下です。
入力例 2
5 10 10 20 100 110 120
出力例 2
3
入力例 3
11 7 21 10 3 19 28 12 11 3 3 15 16
出力例 3
6
Score: 525 points
Problem Statement
You are given a sequence A = (A_1, A_2, \ldots, A_N) of length N.
Find the maximum length of a subsequence of A such that the absolute difference between any two adjacent terms is at most D.
A subsequence of a sequence A is a sequence that can be obtained by deleting zero or more elements from A and arranging the remaining elements in their original order.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 0 \leq D \leq 5 \times 10^5
- 1 \leq A_i \leq 5 \times 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
4 2 3 5 1 2
Sample Output 1
3
The subsequence (3, 1, 2) of A has absolute differences of at most 2 between adjacent terms.
Sample Input 2
5 10 10 20 100 110 120
Sample Output 2
3
Sample Input 3
11 7 21 10 3 19 28 12 11 3 3 15 16
Sample Output 3
6