Bessie criou “Vacas furiosas”, acreditando ser um futuro sucesso e totalmente original. O jogador lança uma vaca com estilingue em cena unidimensional com fardos numa reta numérica. A força ao pousar detona os próximos, podendo causar reação em cadeia. Uma vaca deve detonar todos.

$N$ fardos estão em posições inteiras distintas $x_1, x_2, \ldots, x_N$. Uma vaca com potência $R$ pousando em $x$ gera explosão de “raio $R$”, atingindo $x-R \ldots x+R$. Todos esses fardos explodem simultaneamente com raio $R-1$. Os ainda intactos atingidos explodem depois todos simultaneamente com raio $R-2$, e assim por diante.

Determine a potência mínima $R$ para uma vaca pousando no lugar adequado causar a detonação posterior de todos os fardos.

Entrada

A primeira linha contém $N$ ($2 \leq N \leq 50,000$). As $N$ restantes contêm inteiros $x_1 \ldots x_N$, cada um em $0 \ldots 1,000,000,000$.

Saída

Imprima a potência mínima $R$ para todos os fardos, arredondada com exatamente 1 dígito após o ponto decimal.

Exemplos

Entrada 1

5
8
10
3
11
1

Saída 1

3.0

Nota

No exemplo, potência 3 na posição 5 detona imediatamente 3 e 8. Explodem simultaneamente com raio 2, atingindo 1 e 10; estes simultaneamente com raio 1 atingem o último 11, que explode com raio 0.

Autor do problema: Brian Dean