Hay $n$ fichas de dominó de altura igual $h$ ($h_{\min} \le h \le h_{\max}$) que están colocadas en una fila recta. La $i$-ésima de ellas está colocada en la posición $a_i$.
Lobster y Mobster juegan al siguiente juego. Los jugadores se turnan para derribar fichas de dominó. En cada turno, el jugador actual elige una de las fichas de dominó y luego la derriba hacia la izquierda o hacia la derecha. La ficha cae y posiblemente derriba a otras fichas.
Una ficha de dominó puede derribar a otra si y solo si la distancia entre ellas (la diferencia de sus posiciones) es estrictamente menor que $h$. Por ejemplo, si una ficha $i$ tiene posición $a_i$ y una ficha $j$ ubicada a la derecha de la ficha $i$ tiene posición $a_j$, y $a_j - a_i < h$, entonces al derribar la ficha $i$ hacia la derecha también se derriba la ficha $j$. Luego, la ficha $j$ puede derribar a la siguiente ficha y así sucesivamente, hasta que la última ficha en la cadena de caída no pueda tocar a la siguiente.
El juego termina cuando todas las fichas han caído. Un jugador gana si derriba la última ficha, y un jugador pierde si en su turno no puede derribar ninguna ficha porque no quedan fichas por derribar.
Lobster realiza el primer movimiento, lo cual le da una ventaja. Por lo tanto, antes del inicio del juego, a Mobster se le permite lanzar un hechizo mágico que cambia las alturas de todas las fichas de $h$ a un número arbitrario $h'$ elegido por Mobster del rango $[h_{\min}, h_{\max}]$ (inclusive).
Los jugadores juegan de manera óptima. Encuentre la altura mínima de las fichas $h'$ que le otorga la victoria a Mobster, o determine si cualquier $h'$ conduce a la derrota de Mobster.
Entrada
La primera línea contiene los enteros $n$, $h_{\min}$ y $h_{\max}$ ($1 \le n \le 10^5$, $1 \le h_{\min} \le h_{\max} \le 10^9$).
La segunda línea contiene $n$ enteros. El $i$-ésimo de ellos es la posición $a_i$ de la $i$-ésima ficha ($-10^9 \le a_i \le 10^9$). Se garantiza que las posiciones de todas las fichas son distintas entre sí.
Salida
Imprima la altura mínima $h'$ que le otorga la victoria a Mobster, o imprima "-1" si para cualquier valor $h'$ en el rango $[h_{\min}, h_{\max}]$ Mobster pierde.
Ejemplos
Entrada 1
10 2 5 20 2 22 -4 0 -5 12 5 10 -9
Salida 1
3