시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 21 3 3 50.000%

문제

유진이의 선생님은 유진이에게 몇 개의 문제를 풀라고 주었다. 유진이는 반드시 문제 1번을 먼저 풀어야 한다. 만약에 A번 문제를 풀었을 때, 유진이는 A+1번 문제를 풀거나, A+1번 문제를 건너뛰고 A+2번 문제를 푸는 것도 가능하다. 따라서, 1, 3, 4, 6과 같이 문제를 푸는 것은 가능하지만, 1, 3, 5, 8과 같이 문제를 푸는 것은 불가능하다.

유진이는 문제를 풀면서 흥미를 느낀다. 입력으로 주어지는 P배열은 유진이가 각 문제를 풀 때 느끼는 흥미도를 수치화 한 값이다.

유진이의 선생님은 유진이의 흥미도가 특정 범위내에 들면 문제를 푸는 것을 중지시키려고 한다. 만약 유진이가 지금까지 푼 문제의 흥미도의 최대값과, 최소값의 차이가 V보다 크거나 같으면 문제를 푸는 것을 중지하게 된다. 만약 이런 일이 절대 일어나지 않으면, 유진이는 문제를 다 풀게 된다. 유진이가 풀어야 하는 최소 문제수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 문제의 개수 N과 V가 주어진다. N은 10,000보다 작거나 같고, V도 10,000보다 작거나 같다. 둘째 줄에 유진이가 느끼는 흥미도가 주어진다. 이 값은 문제1번부터 주어진다.

출력

풀어야하는 문제의 최소값을 출력한다.

예제 입력

3 2
1 2 3

예제 출력

2

힌트

출처