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$ - 所有输入均为整数。