18909번 - Circles 스페셜 저지다국어

문제

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}$.

제한

힌트

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\}$.