题目描述

题目译自 JOISC 2024 Day2 T3 「とてもたのしいたのしい家庭菜園 / Growing Vegetables is Fun 5」

进行了多年园艺劳作的 Bitaro 今年春天打算开始种 Bita 草。

Bitaro 准备了 $2N$ 株 Bita 草的幼苗。这些幼苗编号为 $1$ 到 $2N$，并且 Bitaro 计划按这个顺序把幼苗种下去。幼苗 $i\ (1\le i\le 2N)$ 的大小为 $A_i$。Bitaro 想让每一株幼苗获得充足的光照，因此幼苗的大小满足下列条件：

• $A_1\le A_2\le \ldots\le A_N\le A_{N+1}$。
• $A_{N+1}\ge A_{N+2}\ge \ldots \ge A_{2N-1}\ge A_{2N}\ge A_1$。

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

Bitaro 同样准备了 $N$ 个红色花盆和 $N$ 个蓝色花盆，每个花盆也有一个确定的大小。第 $j\ (1\le j\le N)$ 个红色花盆大小为 $B_j$，第 $k\ (1\le k\le N)$ 个蓝色花盆大小为 $C_k$。Bitaro 会将一株 Bita 草的幼苗种在这 $2N$ 个花盆中的一个，并将花盆排成一排，使得幼苗按 $1,2,\ldots,2N$ 的顺序排列。

考虑到外观，这 $2N$ 个花盆必须按照美丽顺序摆放。这里，美丽顺序是一种满足存在连续 $N$ 个花盆颜色相同的花盆摆放顺序。更确切地，一种花盆摆放方式是美丽的，当且仅当存在一个 $1$ 到 $N+1$（包含两边）的整数 $l$，满足幼苗 $l,l+1,\ldots,l+N-1$ 的花盆颜色相同。

当大小为 $y$ 的幼苗种在大小为 $x$ 的花盆中时，种植的难度是这两个数之差的绝对值 $|x-y|$。Bitaro 种植过程的疲劳度是将这 $2N$ 株幼苗种在花盆中的难度的最大值。

给定 Bita 草幼苗和花盆的信息，写一个程序求出当花盆按照美丽顺序摆放时 Bitaro 疲劳度的最小值。

输入格式

第一行一个整数 $N$。

第二行 $2N$ 个整数 $A_1,\ldots,A_{2N}$。

第三行 $N$ 个整数 $B_1,\ldots,B_{N}$。

第四行 $N$ 个整数 $C_1,\ldots,C_{N}$​。

输出格式

输出一行一个整数，表示当花盆按照美丽顺序摆放时 Bitaro 疲劳度的最小值。

2
1 2 6 3
2 5
4 3

2

这组样例中，Bitaro 可以按如下方案种植，疲劳度为 $2$：

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

种有幼苗 $2$ 和 $3$ 的花盆都是蓝色的，所以花盆按照美丽顺序摆放了。

不可能在花盆按美丽顺序摆放的情况下疲劳值小于 $2$，因此输出 $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

这组样例满足子任务 $2,\,3,\,4,\,5$ 的限制。

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

这组样例满足子任务 $2,\,3,\,5$ 的限制。

数据范围与提示

对于全部数据，满足：

• $1\le N\le 3\times 10^5$

• $1\le A_i,B_j,C_k\le 10^9\ (1\le i\le 2N,1\le j,k\le N)$

• $A_1\le A_2\le \ldots\le A_N\le A_{N+1}$

• $A_{N+1}\ge A_{N+2}\ge \ldots \ge A_{2N-1}\ge A_{2N}\ge A_1$

详细子任务附加限制及分值如下表所示。