AT_arc129_b.[ARC129B] Range Point Distance

对于一组整数 $l,r,x$，其中 $l \le r$，定义 $dist(l,r,x)$ 为：

• 若 $x < l$，则 $dist(l,r,x) = l - x$
• 若 $l \le x \le r$，则 $dist(l,r,x) = 0$
• 若 $x >r$，则 $dist(l,r,x) = x - r$

可以简要理解为 $x$ 在数轴上到区间 $[l,r]$ 的距离。

现在给定 $N$ 对整数，第 $i$ 对整数形如 $(L_i, R_i)$。对于 $k=1,2,\dots,N$，分别求解下面的问题：

• 自由选择一个整数 $x$，计算 $max_{i=1}^k dist(L_i,R_i,x)$，求其可能的最小值。

第一行一个整数 $N$，表示给定 $N$ 对整数。

接下来 $N$ 行每行两个整数 $L_i,R_i$。

共 $N$ 行，依次输出 $k=1,2,\dots,N$ 时的答案，输出一个答案换一行。

• $1 \le N \le 2 \times 10^5$
• $1 \le L_i \le R_i \le 10^9$
• 所有输入均为整数。