Stacking Books

There are N rectangles. Rectangle i has mass m_i, length 2, and height h. They are stacked on a two-dimensional plane as follows.

• Every side of every rectangle is parallel to an axis.
• The y-coordinates of the lower sides are all different, and are 0, h, 2h, 3h, ..., (N-1)h.
• The lowest rectangle has lower-left coordinate (-2, 0) and lower-right coordinate (0, 0).

The x-center of a rectangle is the midpoint of its lower side.

For one or more rectangles, their center of mass is computed from their x-centers and masses as follows.

[ \text{center of mass} = \frac{\sum_i m_i \cdot (\text{x-center of rectangle } i)}{\sum_i m_i} ]

A stack is stable if, for every rectangle A that has at least one rectangle above it, the distance between A's x-center and the center of mass of all rectangles above A is at most 1.

If the rectangles are stacked stably, they will not fall. In the left figure the stack is not stable, because the distance between the center of mass of the top two rectangles and the x-center of the rectangle immediately below them is greater than 1. The right figure shows a stable stack.

Given the masses of all rectangles, find the largest possible x-coordinate among all rightmost vertices of the rectangles. The stack must be stable, and the rectangles must be stacked in the input order.

The first line contains the number of rectangles N. (2 <= N <= 300,000)

Each of the next N lines contains one rectangle mass, listed from the lowest rectangle to the highest rectangle. Each mass is a positive integer at most 10,000.

Print the largest possible x-coordinate of a rightmost vertex among all stable stacks. An absolute or relative error of at most 0.000001 is accepted.