12. 贪吃的猪

Problem L. 贪吃的猪

小高开了一家餐厅，每天厨师会列出 $n$ 道菜，第 $i$ 道菜的售价为 $A_i$。

小高希望客人吃得更优惠，因此他决定删除一段连续的菜品（即一个连续子数组），但删除后必须至少保留第一道菜和最后一道菜（不能删除头尾菜品）。

删除后，剩下的菜品按原顺序排列，小高希望这些剩余菜品的平均售价尽可能低。

请你计算这个最低的平均售价。

Input

第一行一个整数 $n$ $(2 \le n \le 10^5)$。

第二行包含 $n$ 个整数 $A_1, A_2, \dots, A_n$ $(1 \le A_i \le 10^9)$。

Output

输出一个实数，表示最低平均售价。

当且仅当你的答案和正确答案的绝对误差或相对误差不超过 $10^{-4}$ 时，答案被视为正确。即：

Example

样例输入1

6
100 1 100 100 2 100

样例输出1

50.75

Note

删除区间 $[3,4]$ 后，剩余菜品为 $100,1,2,100$，平均售价为 $50.75$，这是最优结果。

来源

郑州轻工业大学“筑梯杯”第十八届程序设计大赛暨省内高校邀请赛 L

数据来源：ChenBp