Bessie entwickelte „Wütende Kühe“, ihrer Meinung nach ein völlig origineller künftiger Hit. Der Spieler schießt eine Kuh mit einer Schleuder in eine eindimensionale Szene mit Heuballen auf einer Zahlengeraden. Die Landung sprengt nahe Ballen und kann eine Kettenreaktion auslösen. Eine Kuh soll alle Ballen sprengen.

$N$ Ballen liegen an verschiedenen ganzzahligen Positionen $x_1, x_2, \ldots, x_N$. Eine Kuh mit Stärke $R$ landet bei $x$ und erzeugt eine Explosion mit „Radius $R$“, die $x-R \ldots x+R$ erfasst. Diese Ballen explodieren alle gleichzeitig mit Radius $R-1$. Erfasste noch nicht explodierte Ballen explodieren dann alle gleichzeitig mit Radius $R-2$, und so weiter.

Bestimme die minimale Stärke $R$, mit der eine Kuh an einem geeigneten Ort schließlich alle Ballen sprengt.

Eingabe

Die erste Zeile enthält $N$ ($2 \leq N \leq 50,000$). Die übrigen $N$ enthalten ganze Zahlen $x_1 \ldots x_N$, jede in $0 \ldots 1,000,000,000$.

Ausgabe

Gib die minimale Stärke $R$ für alle Ballen aus, gerundet mit genau 1 Ziffer nach dem Dezimalpunkt.

Beispiele

Eingabe 1

5
8
10
3
11
1

Ausgabe 1

3.0

Hinweis

Im Beispiel sprengt Stärke 3 bei Position 5 sofort 3 und 8. Sie explodieren gleichzeitig mit Radius 2 und erfassen 1 und 10; diese gleichzeitig mit Radius 1 erfassen den letzten 11, der mit Radius 0 explodiert.

Aufgabenautor: Brian Dean