Problem Description

Bitaro, who has been passionate about gardening for many years, plans to start growing a plant called Bita-radish from this spring.

Bitaro has prepared $2N$ Bita-radish seedlings. These seedlings are numbered from $1$ to $2N$, and Bitaro plans to grow them in this order. The size of the $i$-th seedling ($1 \leq i \leq 2N$) is $A_i$. Bitaro wants every seedling to receive enough sunlight, so the seedling sizes 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 has also prepared $N$ red pots and $N$ blue pots, and each pot also has a 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 plants one Bita-radish seedling in each of these $2N$ pots, and arranges the pots in some order, so that seedlings are put into the pots in the order $1,2,\ldots,2N$.

For appearance, these $2N$ pots must be arranged in an aesthetic order. Here, an aesthetic order means that in the arrangement there exist $N$ consecutive pots of the same color. More precisely, an arrangement of pots is called aesthetic if and only if there exists an integer $l$ with $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 growing Bita-radish is the maximum cultivation difficulty among the $2N$ pot-seedling pairs. Write a program that, given the information about the Bita-radish seedlings and the pots, finds the minimum possible value of Bitaro's workload, under the requirement that the pots must be arranged in an aesthetic order.

Input Format

Read the following data from standard input:

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

Output Format

Output one value: the minimum possible value of Bitaro's workload when planting the seedlings so that the pots are arranged in an aesthetic order.

2
1 2 6 3
2 5
4 3

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

8

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

3

Hint

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 of this pair is $|2 - 1| = 1$.
• Plant seedling $2$ in the second blue pot. The cultivation difficulty of this pair is $|3 - 2| = 1$.
• Plant seedling $3$ in the first blue pot. The cultivation difficulty of this pair is $|4 - 6| = 2$.
• Plant seedling $4$ in the second red pot. The cultivation difficulty of this pair is $|5 - 3| = 2$.

The pots containing seedlings $2$ and $3$ are both blue, so the pots are arranged in an aesthetic order.

When planting seedlings so that the pots are arranged in an aesthetic order, it is impossible to achieve a workload smaller than $2$. Therefore, the output is $2$.

This sample input satisfies the constraints of all subtasks.

Sample Explanation 2

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

Sample Explanation 3

This sample input satisfies the constraints of 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 values $A_i$ are distinct. In addition, $A_N < A_{2N}$ holds.
5. (33 points) No additional constraints.

Translated by ChatGPT 5