Hay $N$ robots en una circunferencia. La posición más al norte se numera $0$. Se divide la circunferencia en $M$ partes iguales ($M \ge N$) y los demás puntos de división se numeran del $1$ al $M-1$ en sentido horario. Así se definen las posiciones del $0$ al $M-1$ (figura 1). Inicialmente, los robots ocupan $N$ posiciones distintas.

La distancia entre dos posiciones $x,y$ se define como $y-x$ ($y \ge x$). Un robot $R_i$ en la posición $x_i$ puede vigilar puntos dentro de un alcance fijo $R>0$ en ambos sentidos. Si $a$ es la posición a distancia $R$ de $x_i$ en sentido antihorario y $b$ la posición a distancia $R$ en sentido horario, el robot $R_i$ vigila la parte de la circunferencia de $a$ a $b$ en sentido horario.

Queremos vigilar toda la circunferencia. Las posiciones iniciales pueden dejar partes sin vigilancia, por lo que queremos mover los robots para cubrirla por completo. Suponemos $M \le 2RN$, lo que garantiza que siempre exista tal movimiento.

Los robots solo pueden moverse a las posiciones definidas anteriormente, y cada robot puede moverse como máximo una vez. Queremos minimizar la mayor distancia recorrida por un robot.

Por ejemplo, en la figura 1, los tres robots $R_1,R_2,R_3$ están en las posiciones $1,2,5$, respectivamente, y su alcance es $R=2$. Para vigilar toda la circunferencia, $R_1$ se mueve a la posición $0$ y $R_3$ a la posición $6$. Este movimiento minimiza la mayor distancia recorrida.

Figura 1

Dadas las posiciones de $N$ robots, su alcance $R$ y el entero $M$, encuentra e imprime el mínimo valor posible de la máxima distancia recorrida al moverlos para vigilar toda la circunferencia.

Entrada

La entrada estándar proporciona lo siguiente. La primera línea contiene el número de robots $N$ ($1 \le N \le 1,000,000$). La segunda contiene dos enteros $R,M$ que definen el alcance de vigilancia y las posiciones de la circunferencia ($1 \le R,M \le 10^9$, $N \le M \le 2RN$). La siguiente contiene $N$ enteros distintos $x_i$ ($0 \le x_i \le M-1$, $i=1,\ldots,N$), separados por espacios, que indican las posiciones iniciales de los robots.

Subtareas

• Subtarea 1: 10 de 100 puntos; $M \le 10$.

• Subtarea 2: 30 de 100 puntos; $N \le 7,000$.

• Subtarea 3: 60 de 100 puntos; sin restricciones además de las originales.

Salida

Imprime en la salida estándar el mínimo valor posible de la máxima distancia recorrida por los robots para vigilar toda la circunferencia.

Ejemplos

Entrada 1

3
2 10
1 2 5

Salida 1

1

Entrada 2

6
1 11
0 1 2 3 4 5

Salida 2

2