题目描述

对于整数 $l$、$r$ 和 $x$（$l \\leq r$），我们定义 $dist(l,r,x)$ 如下：

• 如果 $x<l$：$dist(l,r,x)=l-x$
• 如果 $l \\leq x \\leq r$：$dist(l,r,x)=0$
• 如果 $r<x$：$dist(l,r,x)=x-r$

给定 $N$ 对整数，第 $i$ 对为 $(L_i,R_i)$。对于每个 $k=1,2,\\cdots,N$，解决以下问题。

• 任意选择一个整数 $x$，计算 $\\max(dist(L_1,R_1,x),dist(L_2,R_2,x),\\cdots,dist(L_k,R_k,x))$。找到此值的最小可能值。

约束条件

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq L_i \\leq R_i \\leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出输入：

$N$ $L_1$ $R_1$ $L_2$ $R_2$ $\\vdots$ $L_N$ $R_N$

输出

按照 $k=1,2,\\cdots,N$ 的顺序输出答案。

示例输入 1

3
1 3
2 4
5 6

示例输出 1

0
0
1

• 对于 $k=1$，最优选择是 $x=1$。
• 对于 $k=2$，最优选择是 $x=3$。
• 对于 $k=3$，最优选择是 $x=4$。

示例输入 2

10
64 96
30 78
52 61
18 28
9 34
42 86
11 49
1 79
13 59
70 95

示例输出 2

0
0
2
18
18
18
18
18
18
21