题目描述

整数 $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)) $ を計算する． この値としてあり得る最小値を求めよ．

输入格式

入力は以下の形式で標準入力から与えられる．

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

输出格式

各 $k=1,2,\cdots,N$ に対する答えを順番に出力せよ．

题目大意

题目描述

对于一组整数 $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$
• 所有输入均为整数。

3
1 3
2 4
5 6

0
0
1

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

0
0
2
18
18
18
18
18
18
21

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ L_i\ \leq\ R_i\ \leq\ 10^9$
• 入力される値はすべて整数である

Sample Explanation 1

- $k=1$ のときは $x=1$ とすればよいです． - $k=2$ のときは $x=3$ とすればよいです． - $k=3$ のときは $x=4$ とすればよいです．