시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 2 2 2 100.000%

문제

Given an array of non-negative integers $s_1, \ldots, s_n$ with $n \geq 3$, let's call a sequence of $n$ non-negative numbers (not necessarily integers) $x_1, x_2, \ldots, x_n$ \textit{balanced} if for each $i$, the constraint $x_i + x_{i+1} \leq s_i$ is satisfied, where $x_{n+1}=x_1$.

Let's denote $f(s_1, s_2, \ldots, s_n)$ as the largest $x_1 + x_2 + \ldots + x_n$ among all balanced configurations of weights.

You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$. 

Find $n-2$ numbers: $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \ldots, f(a_1, a_2, a_3, \ldots, a_n)$.

입력

The first line contains one integer $n$ ($3 \leq n \leq 100\,000)$.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \leq 100\,000$).

출력

Print $n-2$ numbers: $f(a_1, a_2, a_3), f(a_1, a_2, a_3, a_4), \ldots, f(a_1, a_2, a_3, \ldots, a_n)$.

Your answer will be considered correct if the relative or absolute error of all values in it is at most $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

힌트

In the first example, for the prefix with three elements we can set values $\{10, 10, 10\}$, for the next prefix we can set values $\{10.1, 9.9, 10.1, 4.9\}$.