Conexiones aeropuertarias P30228

En un país lejano todas las ciudades importantes se encuentran curiosamente en diversas posiciones de una misma carretera recta muy larga. Para mejorar los desplazamientos, el gobierno del país ha decidido conectar mediante vuelos directos todas las ciudades que se encuentren al menos a distancia $d$ entre sí. ¿Cuál es la máxima $d$ con la que es posible ir volando desde cualquier ciudad hasta cualquier otra, ya sea directa o indirectamente?

Entrada

La entrada consiste en diversos casos, cada uno con el número de ciudades $n$, seguido de $n$ enteros diferentes con la posición de cada ciudad $p_i$. Podéis suponer $n \ge 2$, $0 \le p_i \le 10^8$, y que las ciudades son comparativamente tan pequeñas que se pueden considerar como puntos en la recta.

Salida

Para cada caso, escribid la máxima $d$ con la que se consigue que todo par de ciudades quede conectado mediante uno o más vuelos.

Puntuación

• test-1:   Entradas donde la diferencia entre la posición máxima y la mínima es como mucho 10, como el Ejemplo.

• test-2:   Entradas donde $n \le 200$.

• test-3:   Entradas donde $n \le 10^5$.