Дан массив неотрицательных целых чисел $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$ среди всех сбалансированных конфигураций весов.

Вам дан массив неотрицательных целых чисел $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\}$.