CF533D.Landmarks

We have an old building with n + 2 columns in a row. These columns support the ceiling. These columns are located in points with coordinates 0 = _x_0 < _x_1 < ... < x__n < x__n + 1. The leftmost and the rightmost columns are special, we will call them bearing, the other columns are ordinary.

For each column we know its durability d__i. Let's consider an ordinary column with coordinate x. Let's assume that the coordinate of the closest to it column to the left (bearing or ordinary) is a and the coordinate of the closest to it column to the right (also, bearing or ordinary) is b. In this task let's assume that this column supports the segment of the ceiling from point to point (here both fractions are considered as real division). If the length of the segment of the ceiling supported by the column exceeds d__i, then the column cannot support it and it crashes after a while, and after that the load is being redistributeed between the neighbouring columns according to the same principle.

Thus, ordinary columns will be crashing for some time until the process stops at some state. One can prove that the set of the remaining columns doesn't depend on the order in which columns crash. If there are only two bearing columns left in the end, then we assume that the whole construction crashes under the weight of the roof. But if at least one ordinary column stays in addition to the bearing ones, then the building doesn't crash.

To make the building stronger, we can add one extra ordinary column of arbitrary durability d' at any (not necessarily integer) point 0 < x' < x__n + 1. If point x' is already occupied by an ordinary column, it is replaced by a new one.

Your task is to find out: what minimal durability can the added column have so that the building doesn't crash?

我们有一座古老的建筑，其屋顶由一排 $ n + 2 $ 根柱子支撑。这些柱子位于坐标点 $ 0 = x_0 < x_1 < \dots < x_n < x_{n+1} $ 处。最左侧与最右侧的柱子是特殊的，我们称其为承重柱；其余柱子为普通柱。

对每根柱子 $ i $，已知其耐久度 $ d_i $。考虑一根位于坐标 $ x $ 的普通柱。设其左侧最近的柱子（承重柱或普通柱）的坐标为 $ a $，右侧最近的柱子（同样为承重柱或普通柱）的坐标为 $ b $。在本题中，我们假定该柱所支撑的屋顶段从点

延伸至点

（此处两个分数均按实数除法计算）。若该柱所支撑的屋顶段长度超过其耐久度 $ d_i $，则该柱无法承受此载荷，将在一段时间后倒塌；此后，其原承担的载荷将根据相同规则重新分配给相邻的柱子。

因此，普通柱将陆续倒塌，直至过程在某一稳定状态停止。可以证明：最终剩余柱子的集合与倒塌顺序无关。若最终仅剩两根承重柱，则认为整座建筑在屋顶重压下彻底坍塌；但若除承重柱外至少还保留一根普通柱，则建筑不会坍塌。

为增强建筑稳定性，我们可在任意位置（不一定是整数坐标）$ 0 < x' < x_{n+1} $ 处额外添加一根普通柱，其耐久度 $ d' $ 可任取。若位置 $ x' $ 上已存在一根普通柱，则用新柱将其替换。

你的任务是：求出所添加柱子所需的最小耐久度 $ d' $，使得建筑不会坍塌。

The first line contains integer n (1 ≤ n ≤ 105) — the number of ordinary columns.

The second line contains n + 2 integers _x_0, _x_1, ..., x__n, x__n + 1 (_x_0 = 0, x__i < x__i + 1 for 0 ≤ i ≤ n, x__n + 1 ≤ 109) — the coordinates of the columns.

The third line contains n integers _d_1, _d_2, ..., d__n (1 ≤ d__i ≤ 109).

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$）—— 普通柱子的数量。

第二行包含 $n+2$ 个整数 $x_0,\ x_1,\ \dots,\ x_n,\ x_{n+1}$（其中 $x_0 = 0$，对所有 $0 \leq i \leq n$ 有 $x_i < x_{i+1}$，且 $x_{n+1} \leq 10^9$）—— 各柱子的坐标。

第三行包含 $n$ 个整数 $d_1,\ d_2,\ \dots,\ d_n$（$1 \leq d_i \leq 10^9$）。

Print a single number — the minimum possible durability of the column that you need to add in order to make the building stay. If you do not have to add the column, please print 0. Your answer will be checked with the relative or absolute error 10 - 4.

输出一个整数——为使建筑保持稳定所需添加的柱子的最小可能耐久度。若无需添加柱子，请输出 0。您的答案将按相对误差或绝对误差 $10^{-4}$ 进行校验。