给定一个包含 $n$ 个非负整数的数组 $s_1, \dots, s_n$（其中 $n \ge 3$），如果一个包含 $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\}$。