配点: 100 点
你听说过 Just Odd Inventions 吗?这家公司的业务就是制造“只是奇怪的发明”。在这里,我们将其缩写为JOI。
JOI 开发了一种新产品“长领带”。领带是 N + 1 有不同的类型,每种类型都有 它们的编号最大为 1 从 N + 1 。i 番目 (1 \leqq i \leqq N + 1) 领带长度类型为 A_i 。
JOI决定召集所有员工,举办一场平局比赛活动。在试衣活动中 N 员工参与,j 人目 (1 \leqq j \leqq N) 的员工最初佩戴的领带长度为 B_j 。
试衣活动将按照以下程序举行。
- 首先,选择一条不会在试衣活动中使用的领带。 1 选择类型。
- 接下来,每位员工从其他领带中选择一条领带进行试戴。 1 选择类型。然而,哪 2 人们还应避免选择同一类型的领带。
- 最后,每位员工摘下他们当前佩戴的领带,并试戴他们之前选择的领带。
长度 一名打着 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 行。
制約
- 1 \leqq N \leqq 200\,000.
- 1 \leqq A_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq N + 1).
- 1 \leqq B_j \leqq 1\,000\,000\,000 (1 \leqq j \leqq N).
小課題
- (1 点) N \leqq 10.
- (8 点) N \leqq 2\,000.
- (91 点)没有额外的限制。
入力例 1
3 4 3 7 6 2 6 4
出力例 1
2 2 1 1
例如,如下举行试穿会。 我们不会使用
- 4 类型的领带。
- 社員 1 是 1 th,员工 选择 2 是 2 th,员工 选择 3 是 3 领带类型。
- 每个员工都试穿衣服。
此时,每个员工依次感受到了异样。 2, 0, 3 因此,这次拟合事件的奇怪之处在于 3 。
通过改变员工选择的领带来减少试穿过程中的奇怪现象。 它可以是 1 。例如,假设您举办如下试穿活动。
- 4 类型的领带。
- 社員 1 是 2 th,员工 选择 2 是 3 th,员工 选择 3 是 1 领带类型。
- 每个员工都试穿衣服。
此时,每个员工依次感受到了异样。 1, 1, 0 因此,这次拟合事件的奇怪之处在于 1 。
这是 当不使用第 4 种领带时,试衣过程中的奇怪程度最小,因此C_4 = 1 。
入力例 2
5 4 7 9 10 11 12 3 5 7 9 11
出力例 2
4 4 3 2 2 2