Étant donné un tableau d'entiers non négatifs $s_1, \dots, s_n$ avec $n \ge 3$, appelons une séquence de $n$ nombres non négatifs (pas nécessairement entiers) $x_1, x_2, \dots, x_n$ équilibrée si pour chaque $i$, la contrainte $x_i + x_{i+1} \le s_i$ est satisfaite, où $x_{n+1} = x_1$.

Désignons par $f(s_1, s_2, \dots, s_n)$ la plus grande valeur de $x_1 + x_2 + \dots + x_n$ parmi toutes les configurations de poids équilibrées.

Vous disposez d'un tableau d'entiers non négatifs $a_1, a_2, \dots, a_n$.

Trouvez $n - 2$ nombres : $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)$.

Entrée

La première ligne contient un entier $n$ ($3 \le n \le 100\,000$).

La deuxième ligne contient $n$ entiers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100\,000$).

Sortie

Affichez $n - 2$ nombres : $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)$.

Votre réponse sera considérée comme correcte si l'erreur relative ou absolue de toutes les valeurs est au plus $10^{-9}$.

Exemples

Entrée 1

4
20 20 20 15

Sortie 1

30.0 35

Entrée 2

6
1 2 1 2 1 2

Sortie 2

2 2 3 3

Entrée 3

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

Sortie 3

1.5 2 3 3 4 5 8 8 9 9

Remarque

Dans le premier exemple, pour le préfixe avec trois éléments, nous pouvons définir les valeurs $\{10, 10, 10\}$, pour le préfixe suivant, nous pouvons définir les valeurs $\{10.1, 9.9, 10.1, 4.9\}$.