Problem A
Blokovi

$N$ rectangles with given masses $m_1, m_2, \ldots , m_ N$, fixed length $l = 2$ and height $h$ are arranged in a Cartesian plane such that:

• rectangle edges are parallel to the coordinate axes;

• the $y$-coordinates of the lower horizontal edges are distinct and assume the following values: $0, h, 2h, 3h, ..., (N - 1)h$;

• the lowest rectangle’s lower left corner has coordinates $(-2, 0)$, while the lower right corner coincides with the origin.

The $X$-centre of a rectangle is the $x$-coordinate of the midpoint of its lower edge. The $X$-barycentre of one or more rectangles is the weighted average of their $X$-centres. It is computed as

In other words, the mass of each rectangle is multiplied by its $X$-centre and the sum of these products is then divided by the total mass of the rectangles.

An arrangement is stable if, for each rectangle $A$, the $X$-barycentre of the set of rectangles above $A$ has distance at most $1$ from the $X$-centre of $A$ (i.e., is contained in the x-interval that covers A).

Intuitively, stability of an arrangement can be understood as the precondition for the arrangement to not fall apart. The arrangement in the figure on the left is unstable since the $X$-barycentre of the top two rectangles falls outside the rectangle underneath (the distance of the $X$-barycentre to the $X$-centre of the underlying rectangle is greater than $1$). The arrangement in the figure on the right is stable.

Given the masses of all rectangles, find the largest (“rightmost”) possible $x$-coordinate of any rectangle corner in a stable arrangement. You are not allowed to change the order of rectangles (they are given from the lowest to the highest one).

Input

The first line of input contains the positive integer $N$ ($2 \le N \le 300\, 000$), the number of rectangles.

Each of the next $N$ lines contains a single positive integer less than $10\, 000$, the mass of a rectangle. The masses are given in order from the lowest to the highest rectangle.

Output

The first and only line of output must contain the required rightmost $x$-coordinate, with an absolute or relative error of at most $10^{-6}$.

2
1
1

1.00000000

3
1
1
1

1.50000000

3
1
1
9

1.90000000