농장의 자루 사이 칸막이

문제

한 농장에서는 수확한 곡식을 자루에 담아 창고의 긴 선반에 올려놓는다. 선반에는 자루를 한 줄로 놓을 수 있으며, 모든 자루에는 곡식을 포함한 무게가 적혀 있다. 농장 일꾼은 무게가 비슷한 자루를 한 구역에서 관리하기 위해, 자루를 정해진 순서로 놓고 필요한 곳에 칸막이를 끼우기로 했다. 먼저 자루 N개를 무게가 가벼운 것부터 무거운 것 순서로 놓는다. 무게가 같은 자루끼리는 어느 자루를 먼저 놓아도 된다. 그다음 나란히 놓인 두 자루 사이를 모두 살펴본다. 오른쪽 자루의 무게에서 왼쪽 자루의 무게를 뺀 값이 기준 D보다 크면 그 사이에 칸막이를 정확히 하나 놓는다. 차이가 D와 같거나 작으면 칸막이를 놓지 않는다. 자루가 없는 위치에 칸막이를 추가하거나, 규칙에 따라 놓아야 하는 칸막이를 생략할 수는 없다. 칸막이가 놓이면 그 양쪽은 서로 다른 구역이 된다. 각 구역에는 자루가 한 개 이상 들어가며, 선반의 양 끝에는 별도의 칸막이를 세지 않는다. 따라서 칸막이가 하나도 필요하지 않으면 모든 자루가 한 구역에 들어간다. 자루가 하나뿐인 경우에도 구역은 하나다. 이 규칙은 정렬한 뒤 바로 이웃한 두 자루의 무게 차이만 비교한다. 같은 구역에서 가장 가벼운 자루와 가장 무거운 자루의 차이가 D보다 커도 상관없다. 예를 들어 무게가 차례로 2, 5, 8이고 D가 3이면, 이웃한 자루의 차이가 모두 3이므로 세 자루는 한 구역에 들어간다. 모든 무게와 기준은 같은 단위로 주어진다. 자루의 무게와 기준 D가 주어질 때, 규칙대로 자루를 놓은 뒤 생기는 구역의 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 자루의 수 N과 기준 D가 공백으로 구분되어 주어진다. N은 1 이상 1,000 이하의 정수이고, D는 0 이상 10,000 이하의 정수다.
둘째 줄에 각 자루의 무게를 나타내는 정수 N개가 공백으로 구분되어 주어진다. 각 무게는 1 이상 10,000 이하이며, 같은 무게가 여러 번 주어질 수 있다.

출력

규칙대로 자루를 배치했을 때 생기는 구역의 수를 정수 하나로 출력한다. 구역의 수는 항상 1 이상이므로 답이 없는 경우는 없다.

6 3
12 3 8 4 15 9

2

7 0
6 2 6 9 2 9 6

3

1 10000
7500

1

출처: Devin.KR 자체 제작