Wesley recibió un arreglo de $N$ elementos $(a_1, a_2, \dots, a_N)$ para Pascua, y está ansioso por ordenarlo (de modo que $a_1 \le a_2 \le \dots \le a_N$).

Aburrido, Wesley decidió complicarse las cosas permitiéndose intercambiar dos elementos solo si la diferencia absoluta entre ellos es menor o igual a $K$. Ten en cuenta que los elementos pueden estar en cualquier posición; siempre y cuando su diferencia absoluta sea menor o igual a $K$, Wesley puede intercambiarlos.

Desafortunadamente, Wesley se dio cuenta rápidamente de que podría no ser posible ordenar el arreglo. Entonces se pregunta: ¿cuál es el valor mínimo de $K$ requerido para poder ordenar el arreglo?

Entrada

La primera línea contiene un entero $N$, el número de elementos en el arreglo ($1 \le N \le 2 \cdot 10^5$).

La siguiente línea contiene $N$ enteros $a_1, a_2, \dots, a_N$, el arreglo en sí ($1 \le a_i \le 10^{18}$).

Salida

Imprime el valor mínimo de $K$ requerido para poder ordenar el arreglo. Si los elementos ya están ordenados, debes imprimir 0.

Ejemplos

Entrada 1

8
1 4 4 2 7 14 12 10

Salida 1

2