Dla danej tablicy nieujemnych liczb całkowitych $s_1, \dots, s_n$, gdzie $n \ge 3$, nazwijmy ciąg $n$ nieujemnych liczb (niekoniecznie całkowitych) $x_1, x_2, \dots, x_n$ zrównoważonym, jeśli dla każdego $i$ spełniony jest warunek $x_i + x_{i+1} \le s_i$, gdzie $x_{n+1} = x_1$.

Niech $f(s_1, s_2, \dots, s_n)$ oznacza największą możliwą sumę $x_1 + x_2 + \dots + x_n$ wśród wszystkich zrównoważonych konfiguracji wag.

Dana jest tablica nieujemnych liczb całkowitych $a_1, a_2, \dots, a_n$. Znajdź $n - 2$ liczby: $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)$.

Wejście

Pierwsza linia zawiera jedną liczbę całkowitą $n$ ($3 \le n \le 100\,000$). Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 100\,000$).

Wyjście

Wypisz $n - 2$ liczby: $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)$. Twoja odpowiedź zostanie uznana za poprawną, jeśli błąd względny lub bezwzględny wszystkich wartości wyniesie co najwyżej $10^{-9}$.

Przykład

Wejście 1

4
20 20 20 15

Wyjście 1

30.0 35

Wejście 2

6
1 2 1 2 1 2

Wyjście 2

2 2 3 3

Wejście 3

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

Wyjście 3

1.5 2 3 3 4 5 8 8 9 9

Uwagi

W pierwszym przykładzie, dla prefiksu z trzema elementami możemy przyjąć wartości $\{10, 10, 10\}$, natomiast dla kolejnego prefiksu możemy przyjąć wartości $\{10.1, 9.9, 10.1, 4.9\}$.