AT_joi2020ho_a 長いだけのネクタイ (Just Long Neckties)

你知道 Just Odd Inventions 公司吗？这家公司的业务就是“只做奇怪的发明（just odd inventions）”。在这里简称为 JOI 公司。 JOI 公司开发了一款新产品“只是很长的领带”。领带共有 $N+1$ 种，每种领带编号为 $1$ 到 $N+1$。第 $i$ 种领带的长度为 $A_i$。 JOI 公司召集了员工，举行了一场领带试穿会。试穿会有 $N$ 名员工参加，第 $j$ 名员工最初佩戴的领带长度为 $B_j$。 试穿会按以下步骤进行： 1. 首先，从所有领带中选择一种不参与试穿会。 2. 接着，每位员工从剩下的领带中选择一种进行试穿。注意，任何两位员工不能选择同一种领带。 3. 最后，每位员工摘下自己原本佩戴的领带，试穿刚才选中的领带。 一名原本佩戴长度为 $b$ 的领带的员工，试穿长度为 $a$ 的领带时，会感受到大小为 $\max\{a-b, 0\}$ 的“奇妙感”。（这里，$\max\{a-b, 0\}$ 表示 $a-b$ 和 $0$ 中较大的那个数。）试穿会中所有员工感受到的“奇妙感”的最大值，称为这场试穿会的**奇妙度**。 当第 $k$ 种领带不参与试穿会时，试穿会可能达到的最小奇妙度记为 $C_k$。 给定每种领带的长度和每位员工最初佩戴的领带长度，请编写程序求出 $C_1, C_2, \ldots, C_{N+1}$ 的值。

输入以如下格式从标准输入读入。所有输入均为整数。 > $N$ $A_1$ $\cdots$ $A_{N+1}$ $B_1$ $\cdots$ $B_N$

请将 $C_1, C_2, \ldots, C_{N+1}$ 的值以空格分隔，输出在一行中。

### 约束条件 - $1 \leq N \leq 200\,000$。 - $1 \leq A_i \leq 1\,000\,000\,000$（$1 \leq i \leq N+1$）。 - $1 \leq B_j \leq 1\,000\,000\,000$（$1 \leq j \leq N$）。 ### 子任务 1.（1 分）$N \leq 10$。 2.（8 分）$N \leq 2\,000$。 3.（91 分）无额外约束。 --- ### 样例解释 1 例如，试穿会可以这样进行： - 不使用第 4 种领带。 - 员工 1 选择第 1 种，员工 2 选择第 2 种，员工 3 选择第 3 种领带。 - 每位员工试穿领带。 此时，每位员工感受到的奇妙感依次为 $2, 0, 3$，因此这场试穿会的奇妙度为 $3$。通过改变员工选择的领带，可以将奇妙度降为 $1$。例如，试穿会可以这样进行： - 不使用第 4 种领带。 - 员工 1 选择第 2 种，员工 2 选择第 3 种，员工 3 选择第 1 种领带。 - 每位员工试穿领带。 此时，每位员工感受到的奇妙感依次为 $1, 1, 0$，因此这场试穿会的奇妙度为 $1$。这就是不使用第 4 种领带时试穿会奇妙度的最小值，所以 $C_4 = 1$。 由 ChatGPT 4.1 翻译