Крыша старинного здания держится на n + 2 колоннах, расположенных в ряд. Колонны расположены в точках 0 = x0 < x1 < ... < xn < xn + 1. Самая левая и самая правая колонны — особенные, мы их будем называть несущими, остальные колонны будем называть обычными.
У каждой обычной колонны известна её прочность di. Рассмотрим некоторую обычную колонну, которая находится в точке x. Пусть координата ближайшей к ней колонны слева (несущей или обычной) — a, а координата ближайшей колонны справа (также несущей или обычной) — b. Будем упрощённо считать, что тогда на эту колонну опирается участок крыши от точки 
до точки 
(в данных формулах подразумевается вещественное деление без округления). Если длина участка крыши, который опирается на колонну, превосходит di, то через некоторое время колонна не выдерживает нагрузки и рушится, при этом нагрузка перераспределяется по соседним колоннам в соответствии с тем же принципом.
Таким образом, некоторое время обычные колонны будут рушиться, пока процесс не остановится в каком-то состоянии. Можно показать, что множество оставшихся колонн не зависит от порядка, в котором происходили обрушения. Если в итоге остаются только две несущих колонны, то считается, что вся конструкция не выдерживает, и здание рушится. Если же остаётся хотя бы одна обычная колонна кроме несущих, то обрушения не происходит.
В целях укрепления конструкции разрешается поставить одну дополнительную обычную колонну произвольной прочности d' в любую (необязательно целочисленную) точку 0 < x' < xn + 1. Если в точке x' уже располагается какая-то из обычных колонн, то она заменяется на новую.
Требуется определить, какой минимальную прочность может иметь добавленная колонна, чтобы здание устояло.
В первой строке находится целое число n (1 ≤ n ≤ 105) — количество обычных колонн.
Во второй строке следуют n + 2 целых числа x0, x1, ..., xn, xn + 1 (x0 = 0, xi < xi + 1 для 0 ≤ i ≤ n, xn + 1 ≤ 109) — координаты колонн.
В третьей строке находятся n целых чисел d1, d2, ..., dn (1 ≤ di ≤ 109).
Выведите единственное число — минимальную возможную прочность колонны, которую надо добавить, чтобы здание устояло. Если добавлять колонну не требуется, выведите 0. Ваш ответ будет проверяться с относительной или абсолютной погрешностью 10 - 4.
2
0 20 40 100
15 40
10
3
0 4 10 28 30
9 13 5
0
