닌자의 방식

모두 알다시피 닌자는 나무 꼭대기에서 다른 나무 꼭대기로 뛰어 이동한다. 어떤 닌자 일족이 나무 사이를 뛰는 훈련을 위해 $N$그루의 나무를 사용하려고 한다. 이들은 가장 낮은 나무에서 출발해 $N-1$번 도약하며, 매번 지금 있는 나무보다 더 높은 나무로 건너뛴다. 훈련이 끝나면 모든 나무를 정확히 한 번씩 밟게 되고, 높이가 낮은 순서대로 지나 마지막에는 가장 높은 나무에 도착한다.

닌자는 한 번의 도약으로 수평 방향 거리 최대 $D$까지만 이동할 수 있다. 훈련을 최대한 즐겁게 만들기 위해, 일족은 가장 낮은 나무와 가장 높은 나무 사이의 수평 거리를 최대한 크게 만들고 싶어 한다.

나무는 다음 규칙에 따라 심는다.

• 모든 나무는 하나의 1차원 경로 위에 심는다.
• 각 나무는 경로 위의 정수 위치에 심으며, 서로 다른 두 나무가 같은 위치에 있을 수 없다.
• 나무를 왼쪽에서 오른쪽으로 놓은 순서는 입력에 주어진 순서와 같아야 한다. 높이순으로 정렬하거나 임의로 순서를 바꿔서는 안 되며, 주어진 순서를 그대로 유지해야 한다.
• 닌자의 도약 거리에는 한계가 있으므로, 모든 나무는 자기 다음으로 높은 나무와 충분히 가깝게 심어야 한다. 즉 두 나무의 수평 위치 차이는 최대 $D$여야 한다(높이 차이는 상관없다).

고정된 순서로 주어진 $N$그루의 나무(각각 서로 다른 정수 높이를 가진다)에 대해, 가장 낮은 나무와 가장 높은 나무 사이의 수평 거리의 최댓값을 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 두 정수 $N$ ($1 \le N \le 1000$)과 $D$ ($1 \le D \le 10^6$)가 담긴 줄로 시작한다. 이어지는 $N$개의 줄에는 나무를 심어야 하는 순서대로 각 나무의 높이가 정수 하나씩 주어진다. 한 테스트 케이스 안에서 모든 높이는 서로 다르다. 마지막 테스트 케이스 뒤에는 두 개의 0이 담긴 줄(0 0)이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 위의 모든 규칙을 지키면서 만들 수 있는, 가장 낮은 나무와 가장 높은 나무 사이의 수평 거리의 최댓값을 출력하되, 유효한 배치가 존재하지 않으면 -1을 출력한다. 답 사이에 빈 줄을 출력하지 않는다.