← 返回题目列表

AtCoder · nadafes2022_day2_l

L. 最小差异最小

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

配点 : 800 点

問題文

长度 小于或等于 N 整数序列 给出 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) 。 对于

区間 [l,r] \,(1 \le l \le r \le N) 的分数定义如下。 找到选择

  • |\min(A_l,A_{l+1},\ldots,A_r)-\min(B_l,B_{l+1},\ldots,B_r)|

k=0,1,\ldots,N-1 , 当我输入r-l=k 小于 [l,r] 时可能的最低分数。 当

制約

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

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

N 行。

i\,(1 \le i \le N) 行中,k=i-1 时输出答案。


入力例 1

3
1 3 4
8 5 7

出力例 1

2
2
4

k=0 时,l=2,r=2 最小化分数。

k=1 时,l=2,r=3 最小化分数。

k=2 时,l=1,r=3 最小化分数。


入力例 2

1
1
1

出力例 2

0

入力例 3

6
3 1 4 1 5 9
2 6 5 3 5 8

出力例 3

0
0
1
1
1
1