# Flat Subsequence SOLUTION ACL CONTEST

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

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

.