로봇

N개의 로봇이 원 위에 놓여 있다. 원 위의 위치는 가장 북쪽을 위치 0으로 하고, 원을 $M$등분하는 나눔점에 시계 방향으로 순서대로 1부터 $M-1$까지 번호를 붙여 정한다. 따라서 위치 0부터 $M-1$까지가 정의된다(그림 1). 로봇들은 처음에 서로 다른 N개의 위치에 놓여 있다.

원 위의 두 위치 x와 y 사이의 거리는 $y - x$ ($y \ge x$)로 정의한다. 로봇 $R_i$가 위치 $x_i$에 있으면, 로봇은 자신을 기준으로 반시계 방향과 시계 방향으로 범위 $R > 0$ 안의 점들을 감시할 수 있다. 위치 $x_i$에서 반시계 방향으로 거리 $R$만큼 떨어진 위치를 $a$, 시계 방향으로 거리 $R$만큼 떨어진 위치를 $b$라 하면, 로봇 $R_i$는 원 위에서 시계 방향으로 $a$에서 $b$까지의 호를 감시한다.

원의 모든 부분을 감시하려고 한다. 처음 위치에서 감시하지 못하는 부분이 있으면 로봇을 옮겨서 원 전체를 감시하도록 한다. $M \le 2RN$이면 원 전체를 감시할 수 있는 이동이 항상 존재한다.

로봇은 위에서 정의한 원 위의 위치로만 이동할 수 있고, 각 로봇은 많아야 한 번만 이동할 수 있다. 로봇들이 이동한 거리의 최댓값을 최소로 하려고 한다.

N, R, M과 로봇들의 초기 위치가 주어질 때, 원 전체를 감시할 수 있도록 로봇을 이동했을 때 최대 이동 거리의 최솟값을 구하시오.

첫 줄에 로봇의 개수를 나타내는 정수 N($1 \le N \le 1{,}000{,}000$)이 주어진다. 둘째 줄에는 감시 범위 R과 원 위의 위치를 정하는 정수 M이 주어진다($1 \le R, M \le 10^9$, $N \le M \le 2RN$). 셋째 줄에는 로봇의 초기 위치를 나타내는 서로 다른 N개의 정수 $x_i$($0 \le x_i \le M-1$)가 공백으로 구분되어 주어진다.

원 전체를 감시할 수 있도록 로봇들을 이동시킬 때, 최대 이동 거리의 최솟값을 출력한다.