Landmarks
Contest: VK Cup 2015 - Round 2
Difficulty rating: 3000

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 = x0 < x1 < ... < xn < xn + 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 di. 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 $${ \frac { a + x } { 2 } }$$ to point $${ \frac { x + b } { 2 } }$$ (here both fractions are considered as real division). If the length of the segment of the ceiling supported by the column exceeds di, 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' < xn + 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?

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

The second line contains n + 2 integers x0, x1, ..., xn, xn + 1 (x0 = 0, xi < xi + 1 for 0 ≤ i ≤ n, xn + 1 ≤ 109) — the coordinates of the columns.

The third line contains n integers d1, d2, ..., dn (1 ≤ di ≤ 109).

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2
0 20 40 100
15 40

Example output:
10

Example input:
3
0 4 10 28 30
9 13 5

Example output:
0

Editorial:
First observation: column crashes only if distance between its neighbours is greater than 2di so it doesn't matter where exactly is this column. The only important thing is how far are left and right neighbour of it.
For every column C let's calculate does there exist subset of columns on the left that everything is stable between C and leftmost bearing column. If answer is yes then how close can be left neighbour of C? Then we will know how far the right neighbour can be. We will use dynamic programming.
Slow approach: For every previous column let's check if it can be neighbours with C. The closest column fulfilling this condition is best left neighbour of C.
Faster approach: Let's denote far[i] as the biggest possible coordinate where right neighbour of column i can be. In our dp we need an extra stack with possible candidates for being left neighbour of new column. In this stack columns are sorted in ascending order by index (and coordinate) and in descending order by far[i]. For every new column we must remove from the top of stack columns which have too low far[i]. Then last column on stack is the best left neighbour and we can calculate value far for current column. It is O(n) algorithm.
Some columns can't be connected with leftmost bearing column and for them we have far[i] = 0. If there exists column with far[i] not less than coordinate of rightmost bearing column then we don't have to add new column and answer is 0.
Ok. Now let's run the same dp from right to the left. Some columns are connected with leftmost bearing column, some other columns with righmost one. And we will want to place new column somewhere between them. Brute force solution is to check every pair of columns and to say: we want these two columns to be neighbours of added column. With values far[i] calculated in dp we check if we can have such a situation and we eventually consider result to be half of a distance between these two columns.
How to make this last part faster? We must create two stacks with best candidates for neighbours of new column. One stack with columns connected to the leftmost column, one with the ones connected to the rightmost one. On these stacks we can find answer with two pointers technique.
Whole solution is linear in time and memory.