Bessie ha creato «Mucche arrabbiate», credendolo un futuro successo completamente originale. Si lancia una mucca con fionda in una scena unidimensionale di balle sulla retta numerica. La forza all'atterraggio detona quelle vicine, forse causando una reazione a catena. Una mucca deve detonare tutte.

$N$ balle sono in posizioni intere distinte $x_1, x_2, \ldots, x_N$. Una mucca con potenza $R$ che atterra in $x$ causa un'esplosione di «raggio $R$», investendo $x-R \ldots x+R$. Tutte queste balle esplodono simultaneamente con raggio $R-1$. Quelle ancora intatte investite esplodono poi tutte simultaneamente con raggio $R-2$, e così via.

Trova la potenza minima $R$ con cui una mucca, atterrando in un luogo adatto, causi infine la detonazione di ogni balla.

Input

La prima riga contiene $N$ ($2 \leq N \leq 50,000$). Le altre $N$ contengono interi $x_1 \ldots x_N$, ciascuno in $0 \ldots 1,000,000,000$.

Output

Stampa la potenza minima $R$ per tutte le balle, arrotondata con esattamente 1 cifra dopo il punto decimale.

Esempi

Input 1

5
8
10
3
11
1

Output 1

3.0

Spiegazione

Nell'esempio, potenza 3 in posizione 5 detona subito 3 e 8. Esplodono simultaneamente con raggio 2, investendo 1 e 10; queste simultaneamente con raggio 1 investono l'ultima 11, che esplode con raggio 0.

Autore del problema: Brian Dean