Stable Rectangle Arrangement

In a 2D Cartesian coordinate system, there are N rectangles, numbered from 1 (bottom) to N (top). The i-th rectangle has:

• a fixed width of 2 and a fixed height h (h is a constant but does not affect the answer),
• mass m_i,
• its edges parallel to the coordinate axes.

The rectangles are placed in order from basic (lowest) to highest; you cannot change their order. The bottom rectangle is fixed so that its bottom‐edge endpoints are at (-2, 0) and (0, 0) (i.e. its bottom center is at -1). For the remaining rectangles, their bottom edges lie on horizontal lines at y = h, 2h, 3h, …, (N-1)h respectively. However, you can shift each rectangle horizontally (that is, you may choose its x coordinate) subject to the following stability condition.

For a single rectangle, we define its X center as the midpoint of its bottom edge. For a group of one or more consecutive rectangles, we define the group’s X center as the weighted average of the individual rectangles’ X centers, where the weight is the rectangle’s mass. In other words, if the group contains rectangles i, i+1, …, N with masses m_i, …, m_N and X centers c_i, …, c_N, then their X center is

$$X_{\text{barycentre}} = \frac{\sum_{j=i}^{N} m_{j}\, c_{j}}{\sum_{j=i}^{N} m_{j}}. $$

The arrangement is said to be stable if for every rectangle (except the top one) the following condition is met: if you consider the block formed by all the rectangles placed above it (i.e. the consecutive group immediately on top), then the absolute difference between the block’s X center and that rectangle’s own X center does not exceed 1. Formally, if rectangle i (1 ≤ i ≤ N-1) supports the block of rectangles i+1, i+2, …, N having weighted average X center X_barycentre, then the stability condition is:

$$\left| X_{\text{barycentre}} - c_{i} \right| \le 1. $$

Your task is to choose horizontal positions for rectangles 2 to N (rectangle 1 is fixed) so that the arrangement is stable, and the maximum x-coordinate among all the rectangles is as large as possible. Note that each rectangle spans from (c_i - 1) to (c_i + 1) on the x-axis. Therefore, the maximum x-coordinate of rectangle i is c_i + 1. Output the maximum possible x-coordinate (over all rectangles) obtainable in a stable arrangement.

Stability Constraint Reformulated

Using the definition above, for each rectangle i (1 ≤ i ≤ N-1), letting S = m_i+1 + m_i+2 + … + m_N and T = m_i+1c_i+1 + m_i+2c_i+2 + … + m_Nc_N, the stability condition becomes:

$$\left| \frac{T}{S} - c_{i} \right| \le 1.$$

To maximize the overall maximum x-coordinate, one may show that the optimal configuration is obtained when every such inequality is tight (i.e. the difference is exactly 1). With c₁ fixed at -1, one can derive recursively that the value of d[1] defined by

$$d[i] = 1 + \frac{\sum_{j=i+1}^{N} m_{j} \; d[j]}{\sum_{j=i+1}^{N} m_{j}}, \quad \text{with } d[N] = 0, $$

must equal the maximum possible x-coordinate among rectangles. (In fact, the top rectangle’s X center becomes X = d[1] - 1, so its right end is at X + 1 = d[1].)

Given the masses m₁, m₂, …, m_N, compute and output d[1].

inputFormat

The input begins with a line containing a single integer N (N ≥ 2) representing the number of rectangles. The next line contains N space‐separated positive numbers representing the masses m₁, m₂, …, m_N.

Note: The first rectangle is fixed with its bottom edge from x = -2 to 0. You may assume that all masses are such that a stable arrangement is possible.

outputFormat

Output a single number: the maximum possible x-coordinate (i.e. the rightmost x coordinate over all rectangles) in a stable arrangement. Answers within a relative or absolute error of 10^-6 will be accepted.

sample

2
5 10

1.000000

</p>