题目描述

Bitaro，一个多年来一直热衷于园艺的人，计划从今年春天开始种植一种名为 Bita-radish 的植物。

Bitaro 已经准备好了 $2N$ 个 Bita-radish 幼苗。这些幼苗从 $1$ 到 $2N$ 编号，Bitaro 计划按照这个顺序进行栽培。第 $i$ 个幼苗（$1 \leq i \leq 2N$）的大小为 $A_i$。Bitaro 希望每个幼苗都能得到足够的阳光，因此幼苗的大小满足以下条件：

• $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$.

注意，幼苗 $1$ 最小，幼苗 $N+1$ 最大。

Bitaro 还准备了 $N$ 个红色花盆和 $N$ 个蓝色花盆，每个花盆也有一定大小。第 $j$ 个（$1 \leq j \leq N$）红色花盆的大小是 $B_j$，第 $k$ 个（$1 \leq k \leq N$）蓝色花盆的大小是 $C_k$。Bitaro 在这总共 $2N$ 个花盆中各种植一株 Bita-radish 幼苗，并按某种顺序排列花盆，使幼苗按 $1,2,...,2N$ 顺序依次放入花盆中。

考虑到外观，这 $2N$ 个花盆必须被安排在一个美观的顺序中。这里，美观的顺序意味着花盆的排列使得存在连续的 $N$ 个花盆颜色相同。更确切地说，一个花盆排列被称为是美观的，当且仅当存在一个整数 $l$，满足 $1 \leq l \leq N+1$，使得种植了幼苗 $l, l+1, \ldots, l+N-1$ 的花盆颜色都相同。

当尺寸为 $y$ 的幼苗种植在尺寸为 $x$ 的花盆中时，该对的栽培难度是绝对值 $|x-y|$。Bitaro 种植 Bita-radish 的工作量是 $2N$ 对花盆和幼苗中的最大栽培难度。编写一个程序，给定 Bita-radish 幼苗和花盆的信息，找到种植幼苗的最小可能 Bitaro 工作量值，并且花盆需要按美观的顺序排列。

输入格式

从标准输入中读取以下数据：

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

输出格式

输出一个值，种植幼苗以使花盆按美观顺序排列时 Bitaro 工作量的最小可能值。

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

提示

样例解释 1

在这个样例输入中，Bitaro 可以通过以下方式种植幼苗来实现工作量为 $2$：

• 将幼苗 $1$ 种植在第一个红色花盆中。这对的栽培难度是 $|2 - 1| = 1$。
• 将幼苗 $2$ 种植在第二个蓝色花盆中。这对的栽培难度是 $|3 - 2| = 1$。
• 将幼苗 $3$ 种植在第一个蓝色花盆中。这对的栽培难度是 $|4 - 6| = 2$。
• 将幼苗 $4$ 种植在第二个红色花盆中。这对的栽培难度是 $|5 - 3| = 2$。

种植了幼苗 $2$ 和 $3$ 的花盆的颜色都是蓝色，因此花盆是按美观顺序排列的。

当种植幼苗以使花盆按美观顺序排列时，无法实现工作量小于 $2$。因此，输出为 $2$。

这个样例输入满足所有子任务的约束条件。

样例解释 2

这个样例输入满足子任务 $2,3,4,5$ 的约束条件。

样例解释 3

这个样例输入满足子任务 $2,3,5$ 的约束条件。

约束条件

• $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$.
• 所有输入值都是整数。

子任务

1. (4 分) $N \leq 5$。
2. (5 分) $N \leq 10$。
3. (21 分) $N \leq 2,000$。
4. (37 分) 所有的 $A_i$ 的值都是不同的。另外，满足 $A_N < A_{2N}$。
5. (33 分) 没有额外的约束条件。