시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 88 33 28 43.077%

문제

"드디어 마지막 나무다!!"

세계적인 갑부 최백준의 정원 관리사 상근이가 외친 말이었다. 백준이네 집의 입구부터 분수까지 거리는 L미터이다. 입구와 분수 사이에는 일직선 도로가 있고, 도로의 폭은 W미터이다.

백준이는 상근이에게 도로의 양쪽에 나무를 심으라고 했다. 가장 첫 나무는 도로의 시작 지점에 있어야 하고, 마지막 나무는 끝 지점에 있어야 한다. 도로의 양쪽에 있는 나무의 위치는 모두 일치해야 한다. 또, 한 쪽 면에 있는 모든 나무 사이의 거리는 같아야 한다.

상근이는 백준이의 말을 정확하게 듣지 않았고, 도로의 왼쪽에만 나무를 심었다. 상근이는 나무를 옮겨 백준이의 요구사항 대로 나무를 심으려고 한다. 백준이의 요구사항을 지키기 위해 옮겨야 하는 나무의 이동 거리의 최소값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 심은 나무의 수 N이 주어진다. N은 짝수이며, 4보다 크거나 같고, 2000보다 작거나 같다. 다음 줄에는 두 정수 L과 W가 주어진다. (1 ≤ L ≤ 10000, 1 ≤ w ≤ 20)  다음 N개 줄에는 나무의 위치 p가 한 줄에 하나씩 주어진다. (0 ≤ p ≤ L)

출력

백준이의 요구사항을 지키기 위해 옮겨야 하는 나무의 이동거리의 최소값을 출력한다. 정답과의 절대/상대 오차가 10-6 이내인 경우에 정답으로 인정된다.

예제 입력 1

4
10 1
1
0
10
10

예제 출력 1

2.4142135624

힌트

W3sicHJvYmxlbV9pZCI6IjUwNDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwOThcdWJiMzQgXHVjNjJlXHVhZTMwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4mcXVvdDtcdWI0ZGNcdWI1MTRcdWM1YjQgXHViOWM4XHVjOWMwXHViOWM5IFx1YjA5OFx1YmIzNFx1YjJlNCEhJnF1b3Q7PFwvcD5cclxuXHJcbjxwPlx1YzEzOFx1YWNjNFx1YzgwMVx1Yzc3OCBcdWFjMTFcdWJkODAgXHVjZDVjXHViYzMxXHVjOTAwXHVjNzU4IFx1YzgxNVx1YzZkMCBcdWFkMDBcdWI5YWNcdWMwYWMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzY3OFx1Y2U1YyBcdWI5ZDBcdWM3NzRcdWM1YzhcdWIyZTQuIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjEyNCBcdWM5ZDFcdWM3NTggXHVjNzg1XHVhZDZjXHViZDgwXHVkMTMwIFx1YmQ4NFx1YzIxOFx1YWU0Y1x1YzljMCBcdWFjNzBcdWI5YWNcdWIyOTQgTFx1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC4gXHVjNzg1XHVhZDZjXHVjNjQwIFx1YmQ4NFx1YzIxOCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHVjNzdjXHVjOWMxXHVjMTIwIFx1YjNjNFx1Yjg1Y1x1YWMwMCBcdWM3ODhcdWFjZTAsIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWQzZWRcdWM3NDAgV1x1YmJmOFx1ZDEzMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWIzYzRcdWI4NWNcdWM3NTggXHVjNTkxXHVjYWJkXHVjNWQwIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWM3M2NcdWI3N2NcdWFjZTAgXHVkNTg4XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjY2FiIFx1YjA5OFx1YmIzNFx1YjI5NCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjMmRjXHVjNzkxIFx1YzljMFx1YzgxMFx1YzVkMCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTU4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHViMDk4XHViYjM0XHViMjk0IFx1YjA1ZCBcdWM5YzBcdWM4MTBcdWM1ZDAgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViM2M0XHViODVjXHVjNzU4IFx1YzU5MVx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1YzcwNFx1Y2U1OFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjZTU4XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWQ1NWMgXHVjYWJkIFx1YmE3NFx1YzVkMCBcdWM3ODhcdWIyOTQgXHViYWE4XHViNGUwIFx1YjA5OFx1YmIzNCBcdWMwYWNcdWM3NzRcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjMzFcdWM5MDBcdWM3NzRcdWM3NTggXHViOWQwXHVjNzQ0IFx1YzgxNVx1ZDY1NVx1ZDU1OFx1YWM4YyBcdWI0ZTNcdWM5YzAgXHVjNTRhXHVjNTU4XHVhY2UwLCBcdWIzYzRcdWI4NWNcdWM3NTggXHVjNjdjXHVjYWJkXHVjNWQwXHViOWNjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWM1YzhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWIwOThcdWJiMzRcdWI5N2MgXHVjNjJlXHVhY2E4IFx1YmMzMVx1YzkwMFx1Yzc3NFx1Yzc1OCBcdWM2OTRcdWFkNmNcdWMwYWNcdWQ1NmQgXHViMzAwXHViODVjIFx1YjA5OFx1YmIzNFx1Yjk3YyBcdWMyZWNcdWM3M2NcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJjMzFcdWM5MDBcdWM3NzRcdWM3NTggXHVjNjk0XHVhZDZjXHVjMGFjXHVkNTZkXHVjNzQ0IFx1YzljMFx1ZDBhNFx1YWUzMCBcdWM3MDRcdWQ1NzQgXHVjNjJlXHVhY2E4XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWIwOThcdWJiMzRcdWM3NTggXHVjNzc0XHViM2Q5IFx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzJlY1x1Yzc0MCBcdWIwOThcdWJiMzRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIFx1YzlkZFx1YzIxOFx1Yzc3NFx1YmE3MCwgNFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAyMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWIyZTQuIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCBMXHVhY2ZjIFdcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IEwgJmxlOyAxMDAwMCwgMSAmbGU7IHcgJmxlOyAyMCkgJm5ic3A7XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjA5OFx1YmIzNFx1Yzc1OCBcdWM3MDRcdWNlNTggcFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgwICZsZTsgcCAmbGU7IEwpPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHViYzMxXHVjOTAwXHVjNzc0XHVjNzU4IFx1YzY5NFx1YWQ2Y1x1YzBhY1x1ZDU2ZFx1Yzc0NCBcdWM5YzBcdWQwYTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzYyZVx1YWNhOFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViMDk4XHViYjM0XHVjNzU4IFx1Yzc3NFx1YjNkOVx1YWM3MFx1YjlhY1x1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MTVcdWIyZjVcdWFjZmNcdWM3NTggXHVjODA4XHViMzAwXC9cdWMwYzFcdWIzMDAgXHVjNjI0XHVjYzI4XHVhYzAwIDEwPHN1cD4tNjxcL3N1cD4gXHVjNzc0XHViMGI0XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWM4MTVcdWIyZjVcdWM3M2NcdWI4NWMgXHVjNzc4XHVjODE1XHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjUwNDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJBc3BlbiBBdmVudWUiLCJkZXNjcmlwdGlvbiI6IjxwPiZxdW90O1BoZXcsIHRoYXQgd2FzIHRoZSBsYXN0IG9uZSEmcXVvdDsgZXhjbGFpbWVkIHRoZSBnYXJkZW4gaGVscGVyIFRpbSBhcyBoZSB0aHJldyB0aGUgbGFzdCB0cmVlIHBsYW50IHRvIHRoZSBncm91bmQuIEhpcyBlbXBsb3llciwgY291bnRlc3MgRXNtZXJhbGRhIEh1bnQgd2hvIG93bmVkIHRoZSBlc3RhdGUsIGhhcyBvcmRlcmVkIGhpbSB0byBhcnJhbmdlIGFuIGF2ZW51ZSBvZiBhc3BlbiB0cmVlcyBhbG9uZyBib3RoIHNpZGVzIG9mIHRoZSBmcm9udCByb2FkIGxlYWRpbmcgdXAgdG8gdGhlIGhvdXNlLiBUaGUgZmlyc3QgdHJlZXMgaW4gdGhlIGF2ZW51ZSBhcmUgc3VwcG9zZWQgdG8gYmUgcGxhbnRlZCBhdCB0aGUgdmVyeSBiZWdpbm5pbmcgb2YgdGhlIHJvYWQsIGFuZCB0aGUgbGFzdCB0cmVlcyBvZiB0aGUgYXZlbnVlIGF0IHRoZSB2ZXJ5IGVuZCBvZiB0aGUgcm9hZC4gVGltLCB3aG8gd2FzIGNvbnN0YW50bHkgYmVpbmcgcmVtaW5kZWQgb2YgaGVyIHNlbnNlIG9mIGFjY3VyYWN5LCBrbmV3IHRoYXQgdGhlIGNvdW50ZXNzIHdvdWxkIGluc2lzdCBvbiB0aGUgdHJlZXMgYmVpbmcgcGxhY2VkIGluIHBlcmZlY3RseSBhbGlnbmVkIHRyZWUgcGFpcnMsIG9uZSBvbiBlYWNoIHNpZGUgb2YgdGhlIHJvYWQsIGFuZCB3aXRoIGV4YWN0bHkgdGhlIHNhbWUgc3BhY2luZyBiZXR3ZWVuIHRoZSBwYWlycyBhbG9uZyB0aGUgcm9hZC4gSG93ZXZlciwgd2hlbiBicmluZ2luZyB0aGUgdHJlZSBwbGFudHMgdG8gdGhlIGVzdGF0ZSwgVGltIGhhZCBqdXN0IGRyb3BwZWQgdGhlbSBhcmJpdHJhcmlseSBhbG9uZyB0aGUgbGVmdCBzaWRlIG9mIHRoZSByb2FkIGFuZCB3YXMgbm93IGZhY2luZyB0aGUgdGFzayBvZiBtb3ZpbmcgdGhlIHRyZWVzIHRvIHRoZWlyIGNvcnJlY3QgcG9zaXRpb25zIHRvIG1lZXQgdGhlIGNvdW50ZXNzJiMzOTtzIHJlcXVpcmVtZW50cy4gQmVpbmcgc3Ryb25nZXIgaW4gbWluZCB0aGFuIGluIGFybXMsIGFuZCBzaW5jZSBpdCB3YXMgdGltZSBmb3IgYSBjbyBlZSBicmVhayBhbnl3YXkgYmVmb3JlIGhlIHN0YXJ0ZWQgZGlnZ2luZywgaGUgc2F0IGRvd24gdG8gZmlndXJlIG91dCB3aGljaCB0cmVlcyB0byBtb3ZlIHRvIHdoaWNoIHBvc2l0aW9ucyBzbyBhcyB0byBtaW5pbWl6ZSB0aGUgdG90YWwgKEV1Y2xpZGVhbikgZGlzdGFuY2UgdGhhdCBoZSBoYWQgdG8gbW92ZSB0aGUgdHJlZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgc3RhcnRzIHdpdGggYSBwb3NpdGl2ZSBldmVuIGludGVnZXIgTiBiZXR3ZWVuIDQgYW5kIDIwMDAgKGluY2x1c2l2ZSksIGdpdmluZyB0aGUgdG90YWwgbnVtYmVyIG9mIHRyZWVzIGluIHRoZSBhdmVudWUuIFRoZSBuZXh0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzIEwgYW5kIFcsIHdoZXJlIDEgJmxlOyBMICZsZTsgMTAwMDAgaXMgdGhlIGxlbmd0aCBvZiB0aGUgcm9hZCwgaW4gbWV0ZXJzLCBhbmQgMSAmbGU7IFcgJmxlOyAyMCBpcyB0aGUgd2lkdGggb2YgdGhlIHJvYWQsIGluIG1ldGVycy4gVGhlIG5leHQgTiBsaW5lcyBlYWNoIGRlc2NyaWJlIHdoZXJlIFRpbSBoYWQgZHJvcHBlZCBvZiB0aGUgdHJlZXMuIEVhY2ggc3VjaCBsaW5lIGNvbnRhaW5zIGFuIGludGVnZXIgMCAmbGU7IHAgJmxlOyBMIGluZGljYXRpbmcgdGhlIHBvc2l0aW9uIG9mIGEgdHJlZSBwbGFudCBhbG9uZyB0aGUgbGVmdCBzaWRlIG9mIHRoZSByb2FkLCBtZWFzdXJlZCBpbiBtZXRlcnMgZnJvbSB0aGUgc3RhcnQgb2YgdGhlIHJvYWQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB0aGUgc21hbGxlc3QgdG90YWwgbnVtYmVyIG9mIG1ldGVycyB0aGUgdHJlZSBwbGFudHMgbmVlZCB0byBiZSBtb3ZlZC4gVGhlIGFuc3dlciBzaG91bGQgYmUgZ2l2ZW4gd2l0aCBhbiBhYnNvbHV0ZSBvciByZWxhdGl2ZSBlcnJvciBvZiBhdCBtb3N0IDEwPHN1cD4tNjxcL3N1cD4uPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d