[JOI 2020 Final] 長いだけのネクタイ

JOI 公司发明了一种领带，一共有 $N+1$ 条领带，编号为 $1$ 到 $N+1$，第 $i$ 条领带的长度为 $A_i$。 JOI 公司开了一个派对，派对中有 $N$ 名员工，第 $j$ 名员工刚开始戴了长度为 $B_j$ 的领带。 派对这样举行： 1. 首先，JOI 公司的老板 JOI 君选出一条领带拿走。 2. 然后，每个员工选一条领带，保证没有两名员工选了相同的领带。 3. 最后，他们取下最先戴的领带，戴上选择的领带。 如果一名员工刚开始戴的领带长度为 $b$，选择的领带长度为 $a$，那么他就会产生 $\max\{a-b,0\}$ 的奇怪感，整场派对的奇怪程度为所有员工的奇怪感的最大值。 于是 JOI 君定义 $C_k$ 为他选出第 $k$ 条领带后的最小奇怪程度。 JOI 君想知道 $C_k$ 的具体值。

第一行一个整数 $N$ 代表员工数。 第二行 $N+1$ 个整数 $A_i$ 代表每个领带的长度。 第三行 $N$ 个整数 $B_j$ 代表每个人最开始戴的领带的长度。

一行 $N+1$ 个整数 $C_k$ 代表选出每个领带后的最小奇怪程度。

3
4 3 7 6
2 6 4

2 2 1 1

5
4 7 9 10 11 12
3 5 7 9 11

4 4 3 2 2 2

#### 样例 1 解释 让我们假设 JOI 君选择了第 $4$ 条领带，那么员工们可以这么选择： - 第 $1$ 名员工选择第 $1$ 条领带，产生奇怪感 $2$ - 第 $2$ 名员工选择第 $2$ 条领带，产生奇怪感 $0$ - 第 $3$ 名员工选择第 $3$ 条领带，产生奇怪感 $3$ 奇怪程度为 $3$。 但我们还可以继续减小奇怪程度： - 第 $1$ 名员工选择第 $2$ 条领带，产生奇怪感 $1$ - 第 $2$ 名员工选择第 $3$ 条领带，产生奇怪感 $1$ - 第 $3$ 名员工选择第 $1$ 条领带，产生奇怪感 $0$ 奇怪程度为 $1$。 因此 $C_4=1$。 #### 数据规模与约定 **本题采用捆绑测试。** - Subtask 1（1 pts）：$N \le 10$。 - Subtask 2（8 pts）：$N \le 2000$。 - Subtask 3（91 pts）：无特殊限制。 对于 $100\%$ 的数据： - $1 \le N \le 2 \times 10^5$。 - $1 \le A_i \le 10^9$。 - $1 \le B_j \le 10^9$。 #### 说明 翻译自 [第19回日本情報オリンピック　本選](https://www.ioi-jp.org/joi/2019/2020-ho/index.html) [A 長いだけのネクタイ](https://www.ioi-jp.org/joi/2019/2020-ho/2020-ho-t1.pdf)。