P10435 [JOIST 2024] 有趣的家庭菜园 5 / Growing Vegetables is Fun 5

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 工作量的最小可能值。

#### 样例解释 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 分) 没有额外的约束条件。