Bessie diseñó «Vacas enfadadas», creyéndolo un futuro éxito y completamente original. Se dispara una vaca con tirachinas a una escena unidimensional de fardos sobre una recta numérica. La fuerza al aterrizar detona los cercanos, pudiendo provocar una reacción en cadena. La meta es usar una vaca para detonar todos.

$N$ fardos están en posiciones enteras distintas $x_1, x_2, \ldots, x_N$. Una vaca con potencia $R$ que aterriza en $x$ explota con «radio $R$», abarcando $x-R \ldots x+R$. Todos esos fardos explotan simultáneamente con radio $R-1$. Los aún intactos alcanzados explotan después todos simultáneamente con radio $R-2$, y así sucesivamente.

Determina la potencia mínima $R$ para que una vaca en un lugar adecuado cause finalmente la detonación de todos los fardos.

Entrada

La primera línea contiene $N$ ($2 \leq N \leq 50,000$). Las $N$ restantes contienen enteros $x_1 \ldots x_N$, cada uno en $0 \ldots 1,000,000,000$.

Salida

Imprime la potencia mínima $R$ para todos los fardos, redondeada con exactamente 1 cifra tras el punto decimal.

Ejemplos

Entrada 1

5
8
10
3
11
1

Salida 1

3.0

Nota

En el ejemplo, potencia 3 en posición 5 detona inmediatamente 3 y 8. Explotan simultáneamente con radio 2, alcanzando 1 y 10; estos simultáneamente con radio 1 alcanzan el último 11, que explota con radio 0.

Autor del problema: Brian Dean