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