$N$ rectangles with given masses $(m_i)$ and equal lengths $(2)$ and heights $(h)$ are arranged in a Cartesian plane such that:

• rectangle edges are parallel to the coordinate axes;
• the y-coordinates of lower horizontal edges are distinct and assume the following values: $0,h,2h,3h,\dots ,(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

$${\displaystyle X\text{-barycentre}=\frac{\sum _i{m}_i\cdot X\text{-centre}(i)}{\sum _i{m}_i}}$$

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 rectangles above $A$ has distance of 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 Specification

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

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

Output Specification

The first and only line of output must contain the required rightmost x-coordinate. The given result must be within $0.000001$ of the official solution.

Scoring

In test cases worth $30\mathrm{\%}$ of points, the rectangles will be ordered from the heaviest to the lightest one.

Sample Input 1

2
1
1

Sample Output 1

1.000000

Sample Input 2

3
1
1
1

Sample Output 2

1.500000

Sample Input 3

3
1
1
9

Sample Output 3

1.900000