Informatica Online Judge

  수입 조작 [0955 / 03BB]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 34   Total Tried : 54


The Champion of this Problem (C++) : gs15120 - 0ms / 1256byte
My Best Submission (C++) : N/A

[Jihak Yoon (koistudy.net)]

Background

경곽이는 요즘 가난하다.
항상 정해진 일자리 없이 일 하다 보니, 수입이 항상 불안정하다.

그러나 부자인 친구 지학이에게는 나름 잘 살고 있는 것처럼 하기 위하여, 수입을 조작하려 한다.

N일 동안의 수익을 나타낸 N개의 수가 주어질 때, 이 중 몇 개를 지워 다음 조건을 모두 만족하게 하려고 한다.

1. 남은 수들은 계속 증가해야 한다.
2. 인접한 수들의 차는 M 이상이 되어야 한다.
3. 가능한 경우가 여러 가지 있다면 길이가 가장 길게 해야 한다.

위 조건을 모두 만족하도록 했을 때, 남은 수들의 갯수를 구하여라.

Input

첫 줄에 N과 M이 공백을 사이에 두고 주어진다. ( 1<=N<=1,000 , 1<=M<=1,000,000,000 )
다음 줄에 N개의 수가 공백을 사이에 두고 주어진다. 이는 N일 동안의 수익이다. 각 수는 1,000,000,000 이하의 자연수이다.

Output

문제에서 요구한 답을 한 줄에 출력한다.

IO Example

입력1

5 2
1 2 3 4 5

출력1

3

입력2

10 1
3 7 5 6 4 9 8 1 2 10

출력2

5

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]