A1456.[COCI-2011_2012-contest5]#1 BLOKOVI

N rectangles with given masses (mi) 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, …, (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 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).

The first line of input contains the positive integer N (2 ≤ N ≤ 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.

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.

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