Bessie stworzyła „Wściekłe krowy”, jej zdaniem przyszły hit o całkowicie oryginalnym pomyśle. Gracz strzela krową z procy na jednowymiarową scenę z belami na osi liczbowej. Siła lądowania wysadza pobliskie bele i może wywołać reakcję łańcuchową. Cel to wysadzić wszystkie jedną krową.

$N$ bel jest w różnych całkowitych pozycjach $x_1, x_2, \ldots, x_N$. Krowa o mocy $R$ lądująca w $x$ powoduje wybuch „promienia $R$”, obejmujący $x-R \ldots x+R$. Bele te wszystkie jednocześnie wybuchają z promieniem $R-1$. Trafione jeszcze niewybuchłe bele potem wszystkie jednocześnie wybuchają z promieniem $R-2$ i tak dalej.

Znajdź minimalną moc $R$, z którą jedna krowa w odpowiednim miejscu spowoduje późniejszy wybuch każdej beli.

Wejście

Pierwszy wiersz zawiera $N$ ($2 \leq N \leq 50,000$). Pozostałe $N$ zawiera całkowite $x_1 \ldots x_N$, każde w $0 \ldots 1,000,000,000$.

Wyjście

Wypisz minimalną moc $R$ dla wszystkich bel, zaokrągloną do dokładnie 1 cyfry po kropce dziesiętnej.

Przykład

Wejście 1

5
8
10
3
11
1

Wyjście 1

3.0

Uwagi

W przykładzie moc 3 w pozycji 5 natychmiast wysadza 3 i 8. Jednocześnie wybuchają z promieniem 2, trafiając 1 i 10; te jednocześnie z promieniem 1 trafiają ostatnią 11, która wybucha z promieniem 0.

Autor zadania: Brian Dean