Há $N$ robôs numa circunferência. A posição mais a norte tem o número $0$. Divide-se a circunferência em $M$ partes iguais ($M \ge N$) e numeram-se os restantes pontos de divisão de $1$ a $M-1$ no sentido horário. Assim se definem as posições de $0$ a $M-1$ (figura 1). Inicialmente, os robôs ocupam $N$ posições distintas.

A distância entre duas posições $x,y$ é definida como $y-x$ ($y \ge x$). Um robô $R_i$ na posição $x_i$ pode vigiar pontos dentro de um alcance fixo $R>0$ em ambos os sentidos. Se $a$ é a posição à distância $R$ de $x_i$ no sentido anti-horário e $b$ a posição à distância $R$ no sentido horário, o robô $R_i$ vigia a parte da circunferência de $a$ até $b$ no sentido horário.

Queremos vigiar toda a circunferência. As posições iniciais podem deixar partes sem vigilância, pelo que queremos mover os robôs para a cobrir por completo. Supomos $M \le 2RN$, garantindo que existe sempre tal movimento.

Os robôs só podem mover-se para as posições definidas acima, e cada robô pode mover-se no máximo uma vez. Queremos minimizar a maior distância percorrida por qualquer robô.

Por exemplo, na figura 1, os três robôs $R_1,R_2,R_3$ estão nas posições $1,2,5$, respetivamente, e o alcance é $R=2$. Para vigiar toda a circunferência, $R_1$ move-se para a posição $0$ e $R_3$ para a posição $6$. Este movimento minimiza a maior distância percorrida.

Figura 1

Dadas as posições de $N$ robôs, o alcance $R$ e o inteiro $M$, encontre e imprima o menor valor possível da máxima distância percorrida ao movê-los para vigiar toda a circunferência.

Entrada

A entrada padrão fornece a seguinte informação. A primeira linha contém o número de robôs $N$ ($1 \le N \le 1,000,000$). A segunda contém dois inteiros $R,M$ que definem o alcance de vigilância e as posições na circunferência ($1 \le R,M \le 10^9$, $N \le M \le 2RN$). A linha seguinte contém $N$ inteiros distintos $x_i$ ($0 \le x_i \le M-1$, $i=1,\ldots,N$), separados por espaços, que indicam as posições iniciais dos robôs.

Subtarefas

• Subtarefa 1: 10 de 100 pontos; $M \le 10$.

• Subtarefa 2: 30 de 100 pontos; $N \le 7,000$.

• Subtarefa 3: 60 de 100 pontos; sem restrições além das originais.

Saída

Imprima na saída padrão o menor valor possível da máxima distância percorrida pelos robôs para vigiar toda a circunferência.

Exemplos

Entrada 1

3
2 10
1 2 5

Saída 1

1

Entrada 2

6
1 11
0 1 2 3 4 5

Saída 2

2