Bessie は大ヒットすると考えるゲーム「怒れる牛」を作り、完全に独創的だと思っています。プレイヤーはパチンコで牛を一次元の数直線上の干し草の束へ飛ばします。着地の力で近くの束が爆発し、さらに連鎖爆発するかもしれません。一頭の牛で全束を爆発させるのが目標です。

$N$ 個の束は異なる整数位置 $x_1, x_2, \ldots, x_N$ にあります。威力 $R$ の牛が $x$ に着地すると「半径 $R$」の爆発が起こり、$x-R \ldots x+R$ の束を巻き込みます。それらはすべて同時に半径 $R-1$ で爆発します。巻き込まれた未爆発の束はすべて同時に半径 $R-2$ で爆発し、以降も同様です。

適切な場所に一頭を着地させて最終的に全束を爆発させる、最小威力 $R$ を求めてください。

入力

最初の行は $N$（$2 \leq N \leq 50,000$）。残る $N$ 行は整数 $x_1 \ldots x_N$、各範囲 $0 \ldots 1,000,000,000$ です。

出力

全束を爆発させる最小威力 $R$ を、四捨五入して小数点以下ちょうど 1 桁で出力してください。

入出力例

入力 1

5
8
10
3
11
1

出力 1

3.0

注記

例で威力 3 の牛が位置 5 に着地すれば 3 と 8 が直ちに爆発。それらが同時に半径 2 で爆発して 1 と 10 を巻き込み、それらが同時に半径 1 で爆発して最後の 11 を巻き込みます。最後は半径 0 で爆発します。

問題作成者：Brian Dean