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

문제

김강산은 서울 신촌에 있는 인공 산이다. 김강산은 사람들이 벽돌을 쌓아서 만들었으며, 등산을 연습하기 위해 만들었다. 사람들은 암벽 등반을 연습하기 위해 김강산에 방문하지만, 김강산은 초심자용이 아니다. 김강산의 관리인 상근이는 사람들이 조금 등반하기 쉽게 산을 조금 고치려고 한다.

김강산은 벽돌이 무더기 n개가 연속되는 형태로 나타낼 수 있고, 각 벽돌 무더기는 벽돌이 hi개 쌓여있는 것이다. 인접한 무더기 사이의 높이 차이는 hi+1 - hi (1 ≤ i ≤ n-1) 이다. 상근이는 모든 높이 차이를 d보다 작거나 같게 만드려고 한다.

상근이는 벽돌 무더기에 벽돌을 더 놓거나 뺄 수 있다. 이 때, 첫 번째 무더기와 마지막 무더기의 벽돌의 개수는 변경할 수 없다. 벽돌을 놓거나 빼는 일은 매우 힘든 일이다. 따라서, 상근이는 이러한 벽돌의 수를 최소로 하려고 한다.

김강산의 정보가 주어졌을 때, 인접한 높이 차이를 d이하로 만들기 위해 놓거나 빼야하는 벽돌 개수의 최소값을 구하는 프로그램을 작성하시오.

입력

입력은 최대 100개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 n과 d가 주어진다. (2 ≤ n ≤ 100, 0 ≤ d ≤ 109) 둘째 줄에는 hi가 주어진다. (0 ≤ hi ≤ 109)

출력

각 테스트 케이스마다 인접한 높이 차이를 d 이하로 만들기 위해 쌓거나 빼야하는 돌의 개수의 최소값을 출력한다. 만약, d이하로 만들 수 없다면 impossible을 출력한다.

예제 입력

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

예제 출력

6
impossible
4

힌트