시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 128 MB 37 12 11 36.667%

문제

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

김강산은 벽돌이 무더기 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+ICgxICZsZTsgaSAmbGU7IG4tMSkgXHVjNzc0XHViMmU0LiBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViYWE4XHViNGUwIFx1YjE5Mlx1Yzc3NCBcdWNjMjhcdWM3NzRcdWI5N2MgZFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVhYzhjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjYmRcdWIzY2MgXHViYjM0XHViMzU0XHVhZTMwXHVjNWQwIFx1YmNiZFx1YjNjY1x1Yzc0NCBcdWIzNTQgXHViMTkzXHVhYzcwXHViMDk4IFx1YmU4NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzRcdWI1NGMsIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHViYjM0XHViMzU0XHVhZTMwXHVjNjQwIFx1YjljOFx1YzljMFx1YjljOSBcdWJiMzRcdWIzNTRcdWFlMzBcdWM3NTggXHViY2JkXHViM2NjXHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWJjYzBcdWFjYmRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC4gXHViY2JkXHViM2NjXHVjNzQ0IFx1YjE5M1x1YWM3MFx1YjA5OCBcdWJlN2NcdWIyOTQgXHVjNzdjXHVjNzQwIFx1YjllNFx1YzZiMCBcdWQ3OThcdWI0ZTAgXHVjNzdjXHVjNzc0XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViY2JkXHViM2NjXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkNWNcdWMxOGNcdWI4NWMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZTQwXHVhYzE1XHVjMGIwXHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTkyXHVjNzc0IFx1Y2MyOFx1Yzc3NFx1Yjk3YyBkXHVjNzc0XHVkNTU4XHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHViMTkzXHVhYzcwXHViMDk4IFx1YmU3Y1x1YzU3Y1x1ZDU1OFx1YjI5NCBcdWJjYmRcdWIzY2MgXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWNkNWNcdWIzMDAgMTAwXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBuXHVhY2ZjIGRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IG4gJmxlOyAxMDAsIDAgJmxlOyBkICZsZTsgMTA8c3VwPjk8XC9zdXA+KSBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IGg8c3ViPmk8XC9zdWI+XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDAgJmxlOyBoPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWM3NzhcdWM4MTFcdWQ1NWMgXHViMTkyXHVjNzc0IFx1Y2MyOFx1Yzc3NFx1Yjk3YyBkIFx1Yzc3NFx1ZDU1OFx1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzMxM1x1YWM3MFx1YjA5OCBcdWJlN2NcdWM1N2NcdWQ1NThcdWIyOTQgXHViM2NjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIGRcdWM3NzRcdWQ1NThcdWI4NWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM1YzZcdWIyZTRcdWJhNzQgaW1wb3NzaWJsZVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY4NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVhc3kgQ2xpbWIiLCJkZXNjcmlwdGlvbiI6IjxwPlNvbWV3aGVyZSBpbiB0aGUgbmVpZ2hib3Job29kIHdlIGhhdmUgYSB2ZXJ5IG5pY2UgbW91bnRhaW4gdGhhdCBnaXZlcyBhIHNwbGVuZGlkIHZpZXcgb3ZlciB0aGUgc3Vycm91bmRpbmcgYXJlYS4gVGhlcmUgaXMgb25lIHByb2JsZW0gdGhvdWdoOiBjbGltYmluZyB0aGlzIG1vdW50YWluIGlzIHZlcnkgZGlmXHVmYjAxY3VsdCwgYmVjYXVzZSBvZiByYXRoZXIgbGFyZ2UgaGVpZ2h0IGRpZmZlcmVuY2VzLiBUbyBtYWtlIG1vcmUgcGVvcGxlIGFibGUgdG8gY2xpbWIgdGhlIG1vdW50YWluIGFuZCBlbmpveSB0aGUgdmlldywgd2Ugd291bGQgbGlrZSB0byBtYWtlIHRoZSBjbGltYiBlYXNpZXIuPFwvcD5cclxuXHJcbjxwPlRvIGRvIHNvLCB3ZSB3aWxsIG1vZGVsIHRoZSBtb3VudGFpbiBhcyBmb2xsb3dzOiB0aGUgbW91bnRhaW4gY29uc2lzdHMgb2YgbiBhZGphY2VudCBzdGFja3Mgb2Ygc3RvbmVzLCBhbmQgZWFjaCBvZiB0aGUgc3RhY2tzIGlzIGg8c3ViPmk8XC9zdWI+IGhpZ2guIFRoZSBzdWNjZXNzaXZlIGhlaWdodCBkaWZmZXJlbmNlcyBhcmUgdGhlcmVmb3JlIGg8c3ViPmkrMTxcL3N1Yj4gJm1pbnVzOyBoPHN1Yj5pPFwvc3ViPiAoZm9yIDEgJmxlOyBpICZsZTsgbiAmbWludXM7IDEpLiBXZSB3b3VsZCBsaWtlIGFsbCBhYnNvbHV0ZSB2YWx1ZXMgb2YgdGhlc2UgaGVpZ2h0IGRpZmZlcmVuY2VzIHRvIGJlIHNtYWxsZXIgdGhhbiBvciBlcXVhbCB0byBzb21lIG51bWJlciBkLjxcL3A+XHJcblxyXG48cD5XZSBjYW4gZG8gdGhpcyBieSBpbmNyZWFzaW5nIG9yIGRlY3JlYXNpbmcgdGhlIGhlaWdodCBvZiBzb21lIG9mIHRoZSBzdGFja3MuIFRoZSBcdWZiMDFyc3Qgc3RhY2sgKHRoZSBzdGFydGluZyBwb2ludCkgYW5kIHRoZSBsYXN0IHN0YWNrICh0aGUgZW5kaW5nIHBvaW50KSBzaG91bGQgcmVtYWluIGF0IHRoZSBzYW1lIGhlaWdodCBhcyB0aGV5IGFyZSBpbml0aWFsbHkuIFNpbmNlIGFkZGluZyBhbmQgcmVtb3Zpbmcgc3RvbmVzIHJlcXVpcmVzIGEgbG90IG9mIGVmZm9ydCwgd2Ugd291bGQgbGlrZSB0byBtaW5pbWl6ZSB0aGUgdG90YWwgbnVtYmVyIG9mIGFkZGVkIHN0b25lcyBwbHVzIHRoZSB0b3RhbCBudW1iZXIgb2YgcmVtb3ZlZCBzdG9uZXMuIFdoYXQgaXMgdGhpcyBtaW5pbXVtIG51bWJlcj88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggdHdvIGludGVnZXJzIG4gKDIgJmxlOyBuICZsZTsgMTAwKSBhbmQgZCAoMCAmbGU7IGQgJmxlOyAxMDxzdXA+OTxcL3N1cD4pOiB0aGUgbnVtYmVyIG9mIHN0YWNrcyBvZiBzdG9uZXMgYW5kIHRoZSBtYXhpbXVtIGFsbG93ZWQgaGVpZ2h0IGRpZmZlcmVuY2UuPFwvbGk+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggbiBpbnRlZ2VycyBoPHN1Yj5pPFwvc3ViPiAoMCAmbGU7IGg8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+KTogdGhlIGhlaWdodHMgb2YgdGhlIHN0YWNrcy48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIHRoZSBtaW5pbXVtIG51bWJlciBvZiBzdG9uZXMgdGhhdCBoYXZlIHRvIGJlIGFkZGVkIG9yIHJlbW92ZWQgb3IgJmxkcXVvO2ltcG9zc2libGUmcmRxdW87IGlmIGl0IGlzIGltcG9zc2libGUgdG8gYWNoaWV2ZSB0aGUgZ29hbC48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==