地标

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

一栋老建筑由一排 $n+2$ 根柱子支撑。柱子坐标满足

$x_0$ 与 $x_{n+1}$ 处是永不倒塌的承重柱，其余为普通柱。普通柱 $i$ 的耐久度为 $d_i$。

若某根普通柱位于 $x$，当前离它最近的左、右柱坐标分别为 $a,b$，则它承担的屋顶长度为 $(b-a)/2$。若该长度严格大于它的耐久度，柱子会倒塌，随后剩余柱子重新分担载荷。最终剩余集合与倒塌顺序无关。

若最终除两根承重柱外至少还剩一根普通柱，建筑不会整体倒塌；否则建筑倒塌。

你可以在任意实数坐标 $0<x'<x_{n+1}$ 处增加一根耐久度为 $d'$ 的普通柱。若该位置已有普通柱，则原柱被替换。求使建筑不会整体倒塌所需的最小 $d'$。若原建筑本来就不会倒塌，输出 $0$。

输入格式

第一行一个整数 $n$。

第二行 $n+2$ 个整数 $x_0,x_1,\ldots,x_{n+1}$。

第三行 $n$ 个整数 $d_1,d_2,\ldots,d_n$。

输出格式

输出最小耐久度。绝对误差或相对误差不超过 $10^{-4}$ 均视为正确。

样例输入 1

2
0 20 40 100
15 40

样例输出 1

10

样例输入 2

3
0 4 10 28 30
9 13 5

样例输出 2

0

数据范围

对于全部数据，$1\le n\le10^5$，$x_0=0$，$0\le x_i<x_{i+1}\le10^9$，$1\le d_i\le10^9$。

每个测试点独立计分。