$n \ge 3$ である非負整数の配列 $s_1, \dots, s_n$ が与えられたとき、$n$ 個の非負数（整数とは限らない）の列 $x_1, x_2, \dots, x_n$ が、すべての $i$ について制約 $x_i + x_{i+1} \le s_i$ を満たすとき、この列を「バランスが取れている」と呼ぶことにします。ただし、$x_{n+1} = x_1$ とします。

$f(s_1, s_2, \dots, s_n)$ を、バランスが取れたすべての重みの構成における $x_1 + x_2 + \dots + x_n$ の最大値と定義します。 非負整数の配列 $a_1, a_2, \dots, a_n$ が与えられます。 $n - 2$ 個の数 $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \dots, f(a_1, a_2, a_3, \dots, a_n)$ を求めてください。

入力

1 行目には整数 $n$ ($3 \le n \le 100\,000$) が含まれます。 2 行目には $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100\,000$) が含まれます。

出力

$n - 2$ 個の数 $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \dots, f(a_1, a_2, a_3, \dots, a_n)$ を出力してください。 出力されたすべての値について、相対誤差または絶対誤差が $10^{-9}$ 以下であれば正解とみなされます。

入出力例

入力 1

4
20 20 20 15

出力 1

30.0 35

入力 2

6
1 2 1 2 1 2

出力 2

2 2 3 3

入力 3

12
1 1 1 3 1 1 2 5 3 2 1 2

出力 3

1.5 2 3 3 4 5 8 8 9 9

注記

最初の例において、3つの要素を持つプレフィックスに対しては値 $\{10, 10, 10\}$ を設定でき、次のプレフィックスに対しては値 $\{10.1, 9.9, 10.1, 4.9\}$ を設定できます。