給定一個包含 $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$ 的最大值。

給定一個包含 $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)$。

輸入格式

第一行包含一個整數 $n$ ($3 \le n \le 100\,000$)。 第二行包含 $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

說明

在第一個範例中，對於包含三個元素的前綴，我們可以設定數值為 $\{10, 10, 10\}$；對於下一個前綴，我們可以設定數值為 $\{10.1, 9.9, 10.1, 4.9\}$。