Junto con el pequeño Kostek, estás construyendo torres con bloques. Ya habéis construido $n$ torres en fila, la $i$-ésima de altura $h_i$. Ahora Kostek quiere establecer un límite entre sus torres y las tuyas. Las torres a la izquierda del límite pertenecerán a Kostek, y las torres restantes a la derecha serán tuyas. Cada uno de vosotros debe tener al menos una torre.
Estáis a punto de pasar al siguiente juego, que comienza cuando cada uno coloca un explorador en su torre más alta. El juego no será divertido si los exploradores están en alturas completamente diferentes. Por lo tanto, debes sugerir la división más justa posible: elige el límite de modo que se minimice el valor absoluto de la diferencia entre la altura de la torre más alta de Kostek y la tuya. Imprime esta diferencia mínima.
Entrada
La primera línea contiene un entero $n$ ($2 \le n \le 300\,000$), que indica el número de torres.
La segunda línea contiene $n$ enteros $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), que indican las alturas de las torres consecutivas de izquierda a derecha.
Salida
Imprime un entero: la menor diferencia de altura posible entre la más alta de tus torres y la más alta de las torres de Kostek.
Ejemplos
Entrada 1
3 200 333 100
Salida 1
133
Entrada 2
5 5 2 4 1 5
Salida 2
0
Entrada 3
6 5 1 4 4 2 3
Salida 3
1
Nota
En la primera prueba, Kostek debería establecer el límite entre las dos primeras torres. Entonces él tiene una torre de altura $200$, mientras que tú tienes torres de alturas $333$ y $100$. Vuestras torres más altas son $200$ y $333$, por lo que el resultado es $133$. No es posible lograr una diferencia menor.
En la segunda prueba, cualquier división da como resultado una diferencia de $0$.
En la tercera prueba, Kostek debería establecer el límite después de la primera, segunda o tercera torre. La diferencia requerida es entonces $|5 - 4| = 1$. El siguiente diagrama muestra una de estas posibilidades óptimas:
