在直角坐标系中放置了 $N$ 个给定质量为 $m_i$、长度均为 $2$、高度均为 $h$ 的矩形，满足以下条件：

• 矩形的边平行于坐标轴；
• 下水平边的 $y$ 坐标互不相同，且取值分别为：$0, h, 2h, 3h, \dots, (N - 1)h$；
• 最下方矩形的左下角坐标为 $(-2, 0)$，而右下角与原点重合。

一个矩形的 X-中心 是其下边中点的 $x$ 坐标。

一个或多个矩形的 X-重心 是它们 X-中心的加权平均值。计算公式如下：

$$Xbarycentre = \frac{\sum_i m_i \cdot Xcentre(i)}{\sum_i m_i}$$

换句话说，将每个矩形的质量乘以其 X-中心，然后将这些乘积之和除以这些矩形的总质量。

如果对于每个矩形 $A$，都满足以下条件，则该放置方案是稳定的：

• $A$ 上方所有矩形的 X-重心与 $A$ 的 X-中心的距离最多为 $1$（即该重心落在覆盖 $A$ 的 $x$ 轴区间内）。

直观上，方案的稳定性可以理解为该结构不会倒塌。左图中的方案是不稳定的，因为最上方两个矩形的 X-重心落在了它们下方的矩形之外（X-重心到下方矩形 X-中心的距离大于 $1$）。右图中的方案是稳定的。

给定所有矩形的质量，求在稳定放置方案中，任何矩形顶点的最大（“最右侧”）可能 $x$ 坐标。你不允许改变矩形的顺序（它们按从最下方到最上方的顺序给出）。

输入格式

输入的第一行包含一个正整数 $N$（$2 \le N \le 300\,000$），表示矩形的数量。

接下来的 $N$ 行，每行包含一个小于 $10\,000$ 的正整数，表示一个矩形的质量。质量按从最下方到最上方矩形的顺序给出。

输出格式

输出的第一行也是唯一一行，应包含所求的最右侧 $x$ 坐标。输出结果与标准答案的绝对误差不能超过 $0.000001$。

子任务

在占总分 30% 的测试数据中，矩形的质量按从重到轻的顺序给出。

样例

输入样例 1

2
1
1

输出样例 1

1.000000

输入样例 2

3
1
1
1

输出样例 2

1.500000

输入样例 3

3
1
1
9

输出样例 3

1.900000