31731번 - Growing Vegetables is Fun 5 서브태스크다국어

Bitaro, who has been enjoying gardening for many years, is planning to grow a plant called Bita-radish starting this spring.

Bitaro has prepared $2N$ Bita-radish seedlings. The seedlings are numbered from $1$ to $2N$, and Bitaro plans to arrange them in this order for cultivation. The size of seedling $i$ ($1 ≤ i ≤ 2N$) is $A_i$. Bitaro wants every seedling to get enough sunlight, so the sizes of the seedlings satisfy the following conditions:

• $A_1 ≤ A_2 ≤ \cdots ≤ A_N ≤ A_{N+1}$.
• $A_{N+1} ≥ A_{N+2} ≥ \cdots ≥ A_{2N-1} ≥ A_{2N} ≥ A_1$.

Note that seedling $1$ is the smallest and seedling $N + 1$ is the largest.

Bitaro has also prepared $N$ red flowerpots and $N$ blue flowerpots, each of which also has a certain size. The size of the $j$-th ($1 ≤ j ≤ N$) red flowerpot is $B_j$, and the size of the $k$-th ($1 ≤ k ≤ N$) blue flowerpot is $C_k$. Bitaro plants one Bita-radish seedling in each of these total $2N$ flowerpots, and arranges the flowerpots in a row so that seedlings $1, 2, \dots, 2N$ are in this order.

Considering the appearance, the $2N$ flowerpots must be arranged in a beautiful order. Here, a beautiful order means an arrangement of flowerpots such that there exist consecutive $N$ flowerpots with the same color. More precisely, an arrangement of flowerpots is said to be a beautiful order if and only if there exists an integer $l$ between $1$ and $N +1$ inclusive such that the colors of the flowerpots planted with seedlings $l, l+1, \dots , l+N -1$ are all the same.

When a seedling of size $y$ is planted in a flowerpot of size $x$, the difficulty of cultivation for that pair is the absolute value $|x−y|$. Bitaro’s workload in growing Bita-radish is the maximum difficulty of cultivation among the $2N$ pairs of flowerpots and seedlings.

Write a program which, given the information about the Bita-radish seedlings and flowerpots, finds the minimum possible value of Bitaro’s workload when planting the seedlings so that the flowerpots are arranged in a beautiful order.

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\cdots$ $A_{2N}$

$B_1$ $B_2$ $\cdots$ $B_N$

$C_1$ $C_2$ $\cdots$ $C_N$

Print a single value ― the minimum possible value of Bitaro’s workload when planting the seedlings so that the flowerpots are arranged in a beautiful order ― in a single line to Standard Output.

• $1 ≤ N ≤ 300\, 000$.
• $1 ≤ A_i ≤ 10^9$ ($1 ≤ i ≤ 2N$).
• $1 ≤ B_j ≤ 10^9$ ($1 ≤ j ≤ N$).
• $1 ≤ C_k ≤ 10^9$ ($1 ≤ k ≤ N$).
• $A_1 ≤ A_2 ≤ \cdots ≤ A_N ≤ A_{N+1}$.
• $A_{N+1} ≥ A_{N+2} ≥ \cdots ≥ A_{2N-1} ≥ A_{2N} ≥ A_1$.
• All input values are integers.