配点 : 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