← 返回题目列表

AtCoder · arc187_d

D. 许多简单的优化

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

定义 成本 树的 一个序列的 X as(最大值 X 减去最小值 X).

给定了序列 A = (A_1, \ldots, A_N) 和 B = (B_1, \ldots, B_N) 长度 N。解决以下问题 k = 1, 2, \ldots, N.

  • 找到序列的最小可能成本 C = (C_1, \ldots, C_k) 谁 i- 第一个元素 C_i is A_i or B_i.

约束

  • 所有输入数字均为整数。
  • 1 \leq N \leq 5 \times 10^5
  • 1 \leq A_i, B_i \leq 10^9

输入

输入由标准输入按以下格式给出:

N 
A_1 \ldots A_N
B_1 \ldots B_N

输出

打印 N 行。

的 i第行 (1 \leq i \leq N) 应包含序列的最小可能成本 C 为 k = i.


示例输入 1

3
8 11 10
7 6 1

示例输出 1

0
1
3

对于 k=1,如果我们选择 C = (8),成本 C is 0,这是最小值。

对于 k=2,如果我们选择 C = (7,6),成本 C is 1,这是最小值。

对于 k=3,如果我们选择 C = (8,11,10),成本 C is 3,这是最小值。


示例输入 2

10
43 35 36 58 25 7 61 4 96 3
55 29 88 15 99 49 67 57 92 49

示例输出 2

0
8
8
23
28
33
36
36
64
64