P8424 [JOI Open 2022] 跷跷板（Seesaw）

**译自 [JOI Open 2022](https://contests.ioi-jp.org/open-2022/index.html) T1. [シーソー](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/seesaw/2022-open-seesaw-statement.pdf) / [Seesaw](http://s3-ap-northeast-1.amazonaws.com/data.cms.ioi-jp.org/open-2022/seesaw/2022-open-seesaw-statement-en.pdf)。**

一根长度为 ${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 + \cdots + b_m}{m}$。 给定 $N$ 和这 $N$ 个砝码的位置 $A_1, A_2, \ldots, A_N$，写一个程序计算箱子的最小可能宽度 $w$。

无

无

**【样例解释 \#1】** 可让箱子的宽度为 $\frac{5}{6}$。我们令 $l = \frac{3}{2}, r = \frac{7}{3}$。进行如下操作： - 最初，重心位置为 $\frac{7}{3}$。 - 第一次操作，我们去掉最右端的砝码（位置为 $4$ 的砝码）。重心位置变为 $\frac{3}{2}$。 - 第二次操作，我们去掉最左端的砝码（位置为 $1$ 的砝码）。重心位置变为 $2$。 在这个过程中，重心始终保持在 $l$ 到 $r$ 范围中。 因为箱子的宽度不会小于 $\frac{5}{6}$，因此输出 $\frac{5}{6}$ 的小数形式。 这组样例满足所有子任务的限制。 ---- **【样例解释 \#2】** 这组样例满足所有子任务的限制。 ---- **【数据范围】** **本题采用捆绑测试。** - 子任务 1（1 分）：$N \le 20$。 - 子任务 2（33 分）：$N \le 100$。 - 子任务 3（33 分）：$N \le 2000$。 - 子任务 4（33 分）：无特殊限制。 对于所有数据，满足 $2 \le N \le 2 \times 10^5$，$0 \le A_1 < A_2 < \cdots < A_N \le {10}^9$。