AT_jsc2019_final_d.Minimize Maximum

给定两个长度为 $N$ 的整数序列 $A_0,A_1,\cdots,A_{N-1}$ 和 $B_0,B_1,\cdots,B_{N-1}$。

对于所有的 $k$（$2\leq k\leq N$），请解决以下问题：

• 构造一个整数序列 $C_0,C_1,\cdots,C_{k-1}$，其中对于所有的 $i$（$0\leq i\leq k-1$），都满足 $A_i\leq C_i\leq B_i$。请问「$C_{i+1}-C_i$（$0\leq i\leq k-2$）的最大值」可能取得的最小值是多少？

输入以如下格式从标准输入读入。

$N$ $A_0$ $A_1$ $\cdots$ $A_{N-1}$ $B_0$ $B_1$ $\cdots$ $B_{N-1}$

请输出 $N-1$ 行。第 $i$（$1\leq i\leq N-1$）行输出当 $k=i+1$ 时问题的答案。

限制条件

• $1\leq N\leq 2\times 10^5$
• $0\leq A_i\leq B_i\leq 10^9$
• 输入的所有值均为整数。

样例解释 1

对于每个 $k$，使「$C_{i+1}-C_i$ 的最大值」最小的整数序列 $C$ 的一组例子如下：

• $k=2$：$C=(2,0)$
• $k=3$：$C=(1,1,1)$
• $k=4$：$C=(1,1,1,2)$

由 ChatGPT 4.1 翻译