Description

一年一度的插(立)旗(flag)大赛又开始了！
比赛场地是一个长度不大于\(10^9\)的街道。居民\(i\)有两个钦定的插旗位置\(x_i, y_i\)，他可以在其中任何一个位置插旗。我们记\(a_i\)为居民\(i\)插旗的位置。我们希望插旗距离相隔最近的两人的距离尽可能大，也就是最大化\(min\{|a_i-a_j|,i\ne j\}\)。你只需要求出这个最大值即可。

Input

输入数据第一行是一个整数\(n\)，表示参加比赛的人数。
接下来\(n\)行，\(i+1\)行有两个整数\(x_i, y_i\)。

Output

输出数据包含一个整数，表示答案。

Sample

Input

2
1 9
3 5

Output

6

Hint

两人分别选择3、9是坠吼的。

数据范围

1. 5%的数据，\(n\le 20\)
2. 另外15%的数据，\(x_i\le y_i\le x_{i+1}\)
3. 另外20%的数据，\(n\le 2000\)，且\(x_1\le x_2\le x_3\le ... \le x_n \le y_n \le y_{n-1} \le ... \le y_1\)
4. 另外25%的数据\(n\le 3000\)
5. 对于100%的数据，\(n\le 2\times 10^4, 0\le x_i,y_i, \le 10^9\)

2s, 512Mb

Source

zrO visit_world Orz