Bessie a conçu « Vaches en colère », qu'elle croit futur succès et totalement original. Le joueur lance une vache à la fronde dans une scène unidimensionnelle de bottes de foin sur une droite numérique. L'impact fait exploser les bottes proches, puis peut déclencher une chaîne d'explosions. Une seule vache doit faire exploser toutes les bottes.

$N$ bottes sont aux positions entières distinctes $x_1, x_2, \ldots, x_N$. Une vache lancée avec puissance $R$ atterrissant en $x$ produit une explosion de « rayon $R$ », touchant $x-R \ldots x+R$. Toutes ces bottes explosent simultanément avec rayon $R-1$. Les bottes encore intactes touchées explosent ensuite toutes simultanément avec rayon $R-2$, et ainsi de suite.

Trouvez la puissance minimale $R$ pour qu'une seule vache atterrissant au bon endroit fasse finalement exploser chaque botte.

Entrée

La première ligne contient $N$ ($2 \leq N \leq 50,000$). Les $N$ restantes contiennent les entiers $x_1 \ldots x_N$, chacun dans $0 \ldots 1,000,000,000$.

Sortie

Affichez la puissance minimale $R$ pour toutes les bottes, arrondie avec exactement 1 chiffre après le point décimal.

Exemples

Entrée 1

5
8
10
3
11
1

Sortie 1

3.0

Remarque

Dans l'exemple, puissance 3 en position 5 fait immédiatement exploser 3 et 8. Elles explosent simultanément avec rayon 2, touchant 1 et 10 ; celles-ci simultanément avec rayon 1 touchent la dernière, 11, qui explose avec rayon 0.

Auteur du problème : Brian Dean