Dado un arreglo de enteros no negativos $s_1, \dots, s_n$ con $n \ge 3$, llamemos a una secuencia de $n$ números no negativos (no necesariamente enteros) $x_1, x_2, \dots, x_n$ equilibrada si para cada $i$ se satisface la restricción $x_i + x_{i+1} \le s_i$, donde $x_{n+1} = x_1$.

Denotemos $f(s_1, s_2, \dots, s_n)$ como la suma máxima $x_1 + x_2 + \dots + x_n$ entre todas las configuraciones equilibradas de pesos.

Se le da un arreglo de enteros no negativos $a_1, a_2, \dots, a_n$.

Encuentre $n - 2$ números: $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)$.

Entrada

La primera línea contiene un entero $n$ ($3 \le n \le 100\,000$).

La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100\,000$).

Salida

Imprima $n - 2$ números: $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)$.

Su respuesta se considerará correcta si el error relativo o absoluto de todos los valores es como máximo $10^{-9}$.

Ejemplos

Entrada 1

4
20 20 20 15

Salida 1

30.0 35

Entrada 2

6
1 2 1 2 1 2

Salida 2

2 2 3 3

Entrada 3

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

Salida 3

1.5 2 3 3 4 5 8 8 9 9

Nota

En el primer ejemplo, para el prefijo con tres elementos podemos establecer los valores $\{10, 10, 10\}$, para el siguiente prefijo podemos establecer los valores $\{10.1, 9.9, 10.1, 4.9\}$.