시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 41 15 11 37.931%

문제

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

김강산은 벽돌이 무더기 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을 출력한다.

예제 입력 1

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

예제 출력 1

6
impossible
4
W3sicHJvYmxlbV9pZCI6IjM2ODUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFlNDBcdWFjMTVcdTVjNzEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWU0MFx1YWMxNVx1YzBiMFx1Yzc0MCBcdWMxMWNcdWM2YjggXHVjMmUwXHVjZDBjXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWM3NzhcdWFjZjUgXHVjMGIwXHVjNzc0XHViMmU0LiBcdWFlNDBcdWFjMTVcdWMwYjBcdWM3NDAgXHVjMGFjXHViNzhjXHViNGU0XHVjNzc0IFx1YmNiZFx1YjNjY1x1Yzc0NCBcdWMzMTNcdWM1NDRcdWMxMWMgXHViOWNjXHViNGU0XHVjNWM4XHVjNzNjXHViYTcwLCBcdWI0ZjFcdWMwYjBcdWM3NDQgXHVjNWYwXHVjMmI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWI5Y2NcdWI0ZTRcdWM1YzhcdWIyZTQuIFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc0MCBcdWM1NTRcdWJjYmQgXHViNGYxXHViYzE4XHVjNzQ0IFx1YzVmMFx1YzJiNVx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVhZTQwXHVhYzE1XHVjMGIwXHVjNWQwIFx1YmMyOVx1YmIzOFx1ZDU1OFx1YzljMFx1YjljYywgXHVhZTQwXHVhYzE1XHVjMGIwXHVjNzQwIFx1Y2QwOFx1YzJlY1x1Yzc5MFx1YzZhOVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YWU0MFx1YWMxNVx1YzBiMFx1Yzc1OCBcdWFkMDBcdWI5YWNcdWM3NzggXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YjRlNFx1Yzc3NCBcdWM4NzBcdWFlMDggXHViNGYxXHViYzE4XHVkNTU4XHVhZTMwIFx1YzI3ZFx1YWM4YyBcdWMwYjBcdWM3NDQgXHVjODcwXHVhZTA4IFx1YWNlMFx1Y2U1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWU0MFx1YWMxNVx1YzBiMFx1Yzc0MCBcdWJjYmRcdWIzY2NcdWM3NzQgXHViYjM0XHViMzU0XHVhZTMwIG5cdWFjMWNcdWFjMDAgXHVjNWYwXHVjMThkXHViNDE4XHViMjk0IFx1ZDYxNVx1ZDBkY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYmMgXHVjMjE4IFx1Yzc4OFx1YWNlMCwgXHVhYzAxIFx1YmNiZFx1YjNjYyBcdWJiMzRcdWIzNTRcdWFlMzBcdWIyOTQgXHViY2JkXHViM2NjXHVjNzc0IGg8c3ViPmk8XC9zdWI+XHVhYzFjIFx1YzMxM1x1YzVlY1x1Yzc4OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJiMzRcdWIzNTRcdWFlMzAgXHVjMGFjXHVjNzc0XHVjNzU4IFx1YjE5Mlx1Yzc3NCBcdWNjMjhcdWM3NzRcdWIyOTQgaDxzdWI+aSsxPFwvc3ViPiAtIGg8c3ViPmk8XC9zdWI+ICgxICZsZTsgaSAmbGU7IG4tMSkgXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE5Mlx1Yzc3NCBcdWNjMjhcdWM3NzRcdWI5N2MgZFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVhYzhjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjYmRcdWIzY2MgXHViYjM0XHViMzU0XHVhZTMwXHVjNWQwIFx1YmNiZFx1YjNjY1x1Yzc0NCBcdWIzNTQgXHViMTkzXHVhYzcwXHViMDk4IFx1YmU4NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YmIzNFx1YjM1NFx1YWUzMFx1YzY0MCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViYjM0XHViMzU0XHVhZTMwXHVjNzU4IFx1YmNiZFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWIyOTQgXHViY2MwXHVhY2JkXHVkNTYwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YmNiZFx1YjNjY1x1Yzc0NCBcdWIxOTNcdWFjNzBcdWIwOTggXHViZTdjXHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVkNzk4XHViNGUwIFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNzc0XHViN2VjXHVkNTVjIFx1YmNiZFx1YjNjY1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWU0MFx1YWMxNVx1YzBiMFx1Yzc1OCBcdWM4MTVcdWJjZjRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzc4XHVjODExXHVkNTVjIFx1YjE5Mlx1Yzc3NCBcdWNjMjhcdWM3NzRcdWI5N2MgZFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjE5M1x1YWM3MFx1YjA5OCBcdWJlN2NcdWM1N2NcdWQ1NThcdWIyOTQgXHViY2JkXHViM2NjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjZDVjXHViMzAwIDEwMFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgblx1YWNmYyBkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBuICZsZTsgMTAwLCAwICZsZTsgZCAmbGU7IDEwPHN1cD45PFwvc3VwPikgXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBoPHN1Yj5pPFwvc3ViPlx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgaDxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVjNzc4XHVjODExXHVkNTVjIFx1YjE5Mlx1Yzc3NCBcdWNjMjhcdWM3NzRcdWI5N2MgZCBcdWM3NzRcdWQ1NThcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWMzMTNcdWFjNzBcdWIwOTggXHViZTdjXHVjNTdjXHVkNTU4XHViMjk0IFx1YjNjY1x1Yzc1OCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBkXHVjNzc0XHVkNTU4XHViODVjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNWM2XHViMmU0XHViYTc0IGltcG9zc2libGVcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2ODUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJFYXN5IENsaW1iIiwiZGVzY3JpcHRpb24iOiI8cD5Tb21ld2hlcmUgaW4gdGhlIG5laWdoYm9yaG9vZCB3ZSBoYXZlIGEgdmVyeSBuaWNlIG1vdW50YWluIHRoYXQgZ2l2ZXMgYSBzcGxlbmRpZCB2aWV3IG92ZXIgdGhlIHN1cnJvdW5kaW5nIGFyZWEuIFRoZXJlIGlzIG9uZSBwcm9ibGVtIHRob3VnaDogY2xpbWJpbmcgdGhpcyBtb3VudGFpbiBpcyB2ZXJ5IGRpZlx1ZmIwMWN1bHQsIGJlY2F1c2Ugb2YgcmF0aGVyIGxhcmdlIGhlaWdodCBkaWZmZXJlbmNlcy4gVG8gbWFrZSBtb3JlIHBlb3BsZSBhYmxlIHRvIGNsaW1iIHRoZSBtb3VudGFpbiBhbmQgZW5qb3kgdGhlIHZpZXcsIHdlIHdvdWxkIGxpa2UgdG8gbWFrZSB0aGUgY2xpbWIgZWFzaWVyLjxcL3A+XHJcblxyXG48cD5UbyBkbyBzbywgd2Ugd2lsbCBtb2RlbCB0aGUgbW91bnRhaW4gYXMgZm9sbG93czogdGhlIG1vdW50YWluIGNvbnNpc3RzIG9mIG4gYWRqYWNlbnQgc3RhY2tzIG9mIHN0b25lcywgYW5kIGVhY2ggb2YgdGhlIHN0YWNrcyBpcyBoPHN1Yj5pPFwvc3ViPiBoaWdoLiBUaGUgc3VjY2Vzc2l2ZSBoZWlnaHQgZGlmZmVyZW5jZXMgYXJlIHRoZXJlZm9yZSBoPHN1Yj5pKzE8XC9zdWI+ICZtaW51czsgaDxzdWI+aTxcL3N1Yj4gKGZvciAxICZsZTsgaSAmbGU7IG4gJm1pbnVzOyAxKS4gV2Ugd291bGQgbGlrZSBhbGwgYWJzb2x1dGUgdmFsdWVzIG9mIHRoZXNlIGhlaWdodCBkaWZmZXJlbmNlcyB0byBiZSBzbWFsbGVyIHRoYW4gb3IgZXF1YWwgdG8gc29tZSBudW1iZXIgZC48XC9wPlxyXG5cclxuPHA+V2UgY2FuIGRvIHRoaXMgYnkgaW5jcmVhc2luZyBvciBkZWNyZWFzaW5nIHRoZSBoZWlnaHQgb2Ygc29tZSBvZiB0aGUgc3RhY2tzLiBUaGUgXHVmYjAxcnN0IHN0YWNrICh0aGUgc3RhcnRpbmcgcG9pbnQpIGFuZCB0aGUgbGFzdCBzdGFjayAodGhlIGVuZGluZyBwb2ludCkgc2hvdWxkIHJlbWFpbiBhdCB0aGUgc2FtZSBoZWlnaHQgYXMgdGhleSBhcmUgaW5pdGlhbGx5LiBTaW5jZSBhZGRpbmcgYW5kIHJlbW92aW5nIHN0b25lcyByZXF1aXJlcyBhIGxvdCBvZiBlZmZvcnQsIHdlIHdvdWxkIGxpa2UgdG8gbWluaW1pemUgdGhlIHRvdGFsIG51bWJlciBvZiBhZGRlZCBzdG9uZXMgcGx1cyB0aGUgdG90YWwgbnVtYmVyIG9mIHJlbW92ZWQgc3RvbmVzLiBXaGF0IGlzIHRoaXMgbWluaW11bSBudW1iZXI/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHR3byBpbnRlZ2VycyBuICgyICZsZTsgbiAmbGU7IDEwMCkgYW5kIGQgKDAgJmxlOyBkICZsZTsgMTA8c3VwPjk8XC9zdXA+KTogdGhlIG51bWJlciBvZiBzdGFja3Mgb2Ygc3RvbmVzIGFuZCB0aGUgbWF4aW11bSBhbGxvd2VkIGhlaWdodCBkaWZmZXJlbmNlLjxcL2xpPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIG4gaW50ZWdlcnMgaDxzdWI+aTxcL3N1Yj4gKDAgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPik6IHRoZSBoZWlnaHRzIG9mIHRoZSBzdGFja3MuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCB0aGUgbWluaW11bSBudW1iZXIgb2Ygc3RvbmVzIHRoYXQgaGF2ZSB0byBiZSBhZGRlZCBvciByZW1vdmVkIG9yICZsZHF1bztpbXBvc3NpYmxlJnJkcXVvOyBpZiBpdCBpcyBpbXBvc3NpYmxlIHRvIGFjaGlldmUgdGhlIGdvYWwuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=