17617번 - 로봇 서브태스크

N개의 로봇들이 원 상에 놓여있다. 원 상의 위치는 가장 북쪽을 위치 0으로 하고 일정한 간격으로 원을 M (≥ N) 등분해서 나뉘는 지점에 시계방향으로 순서대로 위치 1부터 M-1을 부여한다. 그러면 원 상의 위치 0부터 M-1이 정의된다(그림 1). 로봇들은 초기에 서로 다른 N개의 위치에 놓여있다.

원 상에 두 위치 x와 y사이의 거리는 y - x (y ≥ x)로 정의한다. 로봇 R_i가 위치 x_i에 놓여있으면 로봇은 자신으로부터 반시계방향과 시계방향으로 일정한 범위 R > 0안의 점들을 감시할 수 있다. 다시 말해서, 위치 x_i에서 시계 반대방향으로 거리 R 떨어진 위치를 a라 하고, 시계 방향으로 거리 R 떨어진 위치를 b라고 할 때, 로봇 R_i는 원 상의 시계방향으로 위치 a에서 b사이의 부분을 감시할 수 있다.

우리는 원의 모든 부분을 감시하고 싶다. 초기 로봇들의 위치에서 감시하지 못하는 부분이 있을 수 있으므로 이런 경우에 우리는 로봇들을 이동해서 원의 모든 부분 을 감시할 수 있도록 하고 싶다. 우리는 M ≤ 2RN 을 가정함으로써 항상 원의 모든 부분을 감시할 수 있는 로봇들의 이동을 찾을 수 있다.

로봇들은 이동하는 경우 위에 정의된 원 상의 위치로만 이동할 수 있고, 각 로봇마다 많아야 한번만 이동할 수 있다. 이 때, 로봇들이 이동한 거리의 최댓값을 최소화하려고 한다.

예를 들어, 아래 <그림 1>에서 3개 로봇 R₁, R₂, R₃가 각각 위치 1, 2, 5에 놓여있고 감시 범위 R = 2이다. 원의 모든 부분을 감시하기 위해서 로봇 R₁은 위치 0으로 로봇 R₃는 위치 6으로 이동한다. 이것이 로봇들의 이동 거리의 최댓값이 최소가 되는 이동이다.

<그림 1>

N개 로봇들의 위치, 범위 R, 정수 M이 주어질 때, 원의 모든 부분을 감시할 수 있도록 로봇들을 이동할 때, 최대 이동거리의 최솟값을 찾아서 출력하시오.

입력의 첫 줄에는 로봇들의 개수를 나타내는 정수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 로봇의 감시 범위와 원 상의 위치를 정의하는 두 정수 R과 M(1 ≤ R, M ≤ 10⁹, N ≤ M ≤ 2RN)이 주어진다. 다음 줄에 초기 로봇의 위치를 나타내는 서로 다른 N개의 정수 x_i(0 ≤ x_i ≤ M-1, i = 1, ..., N)가 공백을 사이에 두고 주어진다.

원의 모든 부분을 감시할 수 있도록 로봇들의 최대 이동 거리의 최솟값을 출력한다.