Problem Description

Bitaro, an avid gardener for many years, plans to start planting a type of plant called Bita-radish from this spring.

Bitaro has prepared $2N$ Bita-radish seedlings, numbered from $1$ to $2N$, and plans to cultivate them in this order. The size of the $i$-th seedling ($1 \leq i \leq 2N$) is $A_i$. Bitaro wants each seedling to get enough sunlight, so the sizes of the seedlings satisfy the following conditions:

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

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

Bitaro also has $N$ red pots and $N$ blue pots, each with a certain size. The size of the $j$-th ($1 \leq j \leq N$) red pot is $B_j$, and the size of the $k$-th ($1 \leq k \leq N$) blue pot is $C_k$. Bitaro will plant one Bita-radish seedling in each of the $2N$ pots and arrange the pots in a certain order so that the seedlings are placed in the pots in the order $1, 2, ..., 2N$.

Considering the appearance, these $2N$ pots must be arranged in a visually pleasing order. Here, a visually pleasing order means that the arrangement of the pots allows for a sequence of $N$ consecutive pots of the same color. More precisely, a pot arrangement is considered visually pleasing if and only if there exists an integer $l$, satisfying $1 \leq l \leq N+1$, such that the pots containing seedlings $l, l+1, \ldots, l+N-1$ are all of the same color.

When a seedling of size $y$ is planted in a pot of size $x$, the cultivation difficulty of this pair is the absolute value $|x-y|$. Bitaro's workload for planting Bita-radish is the maximum cultivation difficulty among the $2N$ pairs of pots and seedlings. Write a program that, given the information about the Bita-radish seedlings and pots, finds the minimum possible value of Bitaro's workload when the seedlings are planted in a visually pleasing order.

Input Format

Read the following data from the standard input:

• $N$
• $A_1$ $A_2$ ... $A_{2N}$
• $B_1$ $B_2$ ... $B_N$
• $C_1$ $C_2$ ... $C_N$

Output Format

Output a single value, the minimum possible value of Bitaro's workload when the seedlings are planted in a visually pleasing order.

Sample Input and Output

Input Sample #1

2
1 2 6 3
2 5
4 3

Output Sample #1

2

Input Sample #2

9
1 2 3 4 5 6 7 8 9 18 17 16 15 14 13 12 11 10
2 7 4 1 7 6 4 10 6
6 8 9 3 7 1 9 5 4

Output Sample #2

8

Input Sample #3

7
13 16 18 18 21 22 22 23 23 21 19 17 15 14
14 14 20 19 22 17 25
24 15 18 25 24 19 11

Output Sample #3

3

Notes/Hints

Sample Explanation 1

In this sample input, Bitaro can achieve a workload of $2$ by planting the seedlings as follows:

• Plant seedling $1$ in the first red pot. The cultivation difficulty for this pair is $|2 - 1| = 1$.
• Plant seedling $2$ in the second blue pot. The cultivation difficulty for this pair is $|3 - 2| = 1$.
• Plant seedling $3$ in the first blue pot. The cultivation difficulty for this pair is $|4 - 6| = 2$.
• Plant seedling $4$ in the second red pot. The cultivation difficulty for this pair is $|5 - 3| = 2$.

The pots containing seedlings $2$ and $3$ are both blue, so the pots are arranged in a visually pleasing order.

It is not possible to achieve a workload less than $2$ when planting the seedlings in a visually pleasing order. Therefore, the output is $2$.

This sample input satisfies the constraints for all subtasks.

Sample Explanation 2

This sample input satisfies the constraints for subtasks $2, 3, 4, 5$.

Sample Explanation 3

This sample input satisfies the constraints for subtasks $2, 3, 5$.

Constraints

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

Subtasks

1. (4 points) $N \leq 5$.
2. (5 points) $N \leq 10$.
3. (21 points) $N \leq 2,000$.
4. (37 points) All $A_i$ values are distinct. Additionally, $A_N < A_{2N}$.
5. (33 points) No additional constraints.

见题面 Input 部分

见题面 Output 部分