Problem Description

In the Cartesian coordinate system, there are $N$ rectangles with mass $m_i$, length $2$, and height $h$, such that:

• The edges of the rectangles are parallel to the coordinate axes;
• The bottom of each rectangle is at $y$ coordinates $0, h, 2h, 3h, \dots, (N-1)h$;
• The bottom-left corner of the lowest rectangle is at $(-2, 0)$, and its bottom-right corner coincides with the origin.

The X-center of a rectangle is defined as the X-coordinate of the midpoint of its bottom edge. The X-center of one or more rectangles is the weighted average of their X-centers, calculated as:

$$ X_{barycenter} = \frac{\sum_{i} m_i \times X_{center}(i)}{\sum_{i} m_i} $$

where X_barycenter represents the X-center of one or more rectangles, and X_center represents the X-center of a single rectangle.

In other words, it is the sum of each rectangle's mass multiplied by its X-center, divided by the total mass of the rectangles.

A configuration of rectangles is considered stable if, for every rectangle, the distance between its X-center and the X-center of the rectangle directly above it is less than or equal to $1$.

For example, the configuration on the left is unstable because the distance between the X-centers of the top two rectangles and the bottom rectangle is greater than $1$. The configuration on the right is stable.

Given the masses of all rectangles, find the maximum X-coordinate of the rectangles in a stable configuration.

You cannot change the order of the rectangles, which are given from bottom to top.

Input Format

The first line contains an integer $N$, the number of rectangles.

The next $N$ lines each contain an integer $m_i$, the mass of the $i$-th rectangle.

Output Format

A single line containing a decimal number, the answer, accurate to within an error of $0.000001$.

Sample Input and Output

Sample Input #1

2
1
1

Sample Output #1

1.00000000

Sample Input #2

3
1
1
1

Sample Output #2

1.50000000

Sample Input #3

3
1
1
9

Sample Output #3

1.90000000

Notes

For $30\%$ of the test cases, the masses of the rectangles are given in descending order.

$2 \le N \le 3 \times 10^5$, $1 \le m_i \le 10^4$.

This problem is translated from COCI 2011/2012 #5 T5.

见题面 Input 部分

见题面 Output 部分