이동 로봇

요즘 이동 로봇은 여러 산업 현장과 연구 현장에서 흔히 쓰인다. 당신은 매우 길고 좁고 곧은 동굴을 탐사하는 n대의 이동 로봇을 제어하는 임무를 맡았다. 이 동굴은 그냥 직선으로 볼 수 있다. 이동 로봇은 주변 환경에서 데이터를 수집하며, 무한궤도 덕분에 기동성이 뛰어나다. 당신은 관제 데스크에서 무선 제어 시스템으로 n대의 이동 로봇을 제어할 수 있다. 당신이 제어하는 n대의 이동 로봇에는 1부터 n까지 번호가 붙어 있으며, 로봇 1, 로봇 2, …, 로봇 n − 1, 로봇 n으로 구분한다.

이동 로봇은 간단한 적외선 통신 프로토콜로 서로 수집한 데이터를 공유할 수도 있다. 다만 로봇 간 통신은 다음의 매우 엄격한 배치가 n대의 이동 로봇 모두에 대해 완성되었을 때만 작동한다. 모든 i = 1, 2, … , n − 1에 대해 로봇 i와 로봇 i + 1 사이의 거리가 정확히 d여야 한다. 여기서 d는 주어진 양의 실수이고, 두 로봇이 동굴 안 같은 위치에 있어서는 안 된다. 동굴은 매우 길고 매우 좁고 매우 곧아서 양쪽으로 끝없이 뻗은 직선으로 볼 수 있으므로, 동굴 안에서 각 이동 로봇의 위치는 실수 x로 나타낸다. 따라서 두 이동 로봇 사이의 거리는 두 위치의 차로 계산한다.

이동 로봇들은 현재 위치에서 서로 데이터를 공유해야 하며, 당신은 로봇 간 통신을 위해 로봇들을 움직이려 한다. 로봇은 느리고 동굴을 따라 같은 속도로 동시에 움직이므로, 시간을 최대한 아끼기 위해 각 로봇이 이동해야 하는 최대 거리를 최소화하려 한다. 이동 중 두 로봇은 둘 다 동굴 안 같은 위치에 있는 순간 안전하게 서로를 지나친다고 가정한다. 따라서 현재 두 대 이상의 로봇이 동굴 안 같은 위치에 있을 수도 있다.

n대의 이동 로봇의 현재 위치가 주어졌을 때, n대의 로봇 각각이 이동하는 최대 거리를 최소화하는 로봇 간 통신을 위한 새 위치를 계산하고, 그 최소화된 최대 이동 거리를 출력하는 프로그램을 작성하시오.

프로그램은 표준 입력에서 입력을 읽는다. 입력은 정확히 두 줄로 이루어진다. 첫째 줄에는 두 정수 n과 d가 주어진다(2 ≤ n ≤ 1,000,000, 1 ≤ d ≤ 10^10). n은 당신이 제어하는 이동 로봇의 수이고, d는 로봇 간 통신을 위해 로봇들이 유지해야 하는 거리이다. 각 이동 로봇은 1부터 n까지의 번호로 구분한다. 둘째 줄에는 n개의 정수가 주어지며, 각 정수는 −10^16 이상 10^16 이하이고, 로봇 1, 로봇 2, …, 로봇 n의 현재 위치를 이 순서대로 나타낸다.

프로그램은 표준 출력에 출력을 쓴다. 주어진 현재 위치에서 로봇 간 통신을 위해 이동 로봇들이 이동해야 하는 최대 거리의 최솟값을 나타내는 실수 하나를 소수 첫째 자리에서 반올림하여 한 줄에 정확히 출력한다.