题目描述

译自 JOI Open 2022 T1 「シーソー / Seesaw」

一根长度为 $10^9$ 的直杆从左到右水平放置。你可以忽略这根杆的重量。共有 $N$ 个砝码挂在这根杆上，每个砝码的质量为一单位。这 $N$ 个砝码的位置两两不同。第 $i\ (1\le i\le N)$ 个砝码的位置为 $A_i$。即，第 $i$ 个砝码到直杆最左端的距离为 $A_i$。

最开始，我们有一个宽度为 $w$ 的箱子。我们可以把这根杆子放在箱子上，支撑起杆从 $l$ 到 $r\ (0\le l<r\le 10^9)$ 的部分（包括两端），即，从杆上位置为 $l$ 到杆上位置为 $r$ 的区间。这里需要满足 $r=l+w$。之后我们不可以改变 $l$ 和 $r$ 的值。

接下来，我们去掉挂在杆上最左端或最右端的砝码。我们需要重复这个操作 $N-1$ 次。在这个过程中，包括初始状态和最终状态，挂在杆上的所有砝码重心都需要保持在 $l$ 到 $r$ 之间（包括两端）。如果杆上挂有 $m$ 个砝码，位置分别为 $b_1,b_2,\ldots ,b_m$，那么重心位置为 $\frac{b_1+b_2+\ldots+b_m}{m}$。

给定 $N$ 和这 $N$ 个砝码的位置 $A_1,A_2,\ldots,A_N$，写一个程序计算箱子的最小可能宽度 $w$。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $A_1,A_2,\ldots,A_N$。

输出格式

输出箱子的最小可能宽度 $w$。你的程序将被判为正确，如果你的输出与标准答案之间的绝对误差或相对误差小于等于 $10^{-9}$。

3
1 2 4

0.8333333333

6
1 2 5 6 8 9

1.166666667

数据范围与提示

对于所有数据，满足 $2\le N\le 2\times 10^5,0\le A_1<A_2<\ldots<A_N\le 10^9$。

详细子任务附加限制及分值如下表所示。