Page Contents
Flat Subsequence SOLUTION
Problem Statement
You are given a sequence A1,A2,…,AN and an integer K.Print the maximum possible length of a sequence B that satisfies the following conditions:B is a (not necessarily continuous) subsequence of A.For each pair of adjacents elements of B, the absolute difference of the elements is at most K
Constraints
1
≤
N
≤
300
,
000
0
≤
A
i
≤
300
,
000
0
≤
K
≤
300
,
000
All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
K
A
1
A
2
:
A
N
Output
Print the answer.
Sample Input 1
Copy
10 3
1
5
4
3
8
6
9
7
2
4
Sample Output 1
Copy
7
For example,
B
=
(
1
,
4
,
3
,
6
,
9
,
7
,
4
)
satisfies the conditions.
It is a subsequence of
A
=
(
1
,
5
,
4
,
3
,
8
,
6
,
9
,
7
,
2
,
4
)
.
All of the absolute differences between two adjacent elements (
|
1
−
4
|
,
|
4
−
3
|
,
|
3
−
6
|
,
|
6
−
9
|
,
|
9
−
7
|
,
|
7
−
4
|
) are at most
K
=
3
.
