一根长度为 $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, \dots, b_m$，则重心的位置为 $\frac{b_1+b_2+\dots+b_m}{m}$。

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

输入格式

从标准输入读取以下数据。给定值均为整数。

$N$ $A_1 \ A_2 \ \dots \ A_N$

输出格式

向标准输出写入一行。输出应包含盒子的最小可能宽度 $w$。如果输出的相对误差或绝对误差小于或等于 $0.000 \ 000 \ 001 \ (= 10^{-9})$，则你的程序被认为是正确的。输出格式应为以下之一：

• 整数。（例如：123, 0, -2022）
• 由整数、小数点和 0 到 9 之间的数字序列组成的序列。数字之间不应由符号或空格分隔。小数点后的位数没有限制。（例如：123.4, -123.00, 0.00288）

数据范围

• $2 \le N \le 200 \ 000$。
• $0 \le A_1 < A_2 < \dots < A_N \le 1 \ 000 \ 000 \ 000 \ (= 10^9)$。

子任务

1. (1 分) $N \le 20$。
2. (33 分) $N \le 100$。
3. (33 分) $N \le 2 \ 000$。
4. (33 分) 无附加限制。

样例

输入格式 1

3
1 2 4

输出格式 1

0.8333333333

说明

设盒子的宽度为 $\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

6
1 2 5 6 8 9

输出格式 2

1.166666667

说明

该样例输入满足所有子任务的限制。