시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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

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

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

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

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

<그림 1>

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

입력

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

출력

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

예제 입력 1

3
2 10
1 2 5

예제 출력 1

1

예제 입력 2

6
1 11
0 1 2 3 4 5

예제 출력 2

2