Description

小沙在悬崖的底下，他准备爬上悬崖顶上去见小雅。悬崖的高度为 $n$ ，每个高度对应了一个突出度，那么就形成了一个突出度数组 $a_i$ ，悬崖底的突出度为 0。

嘤嘤定义一个悬崖的危险值为：突出度数组 $a$ 中第 $i$ 个元素减第 $i-1$ 个元素之差的最大值，特别的，由于没有第 0 个元素，因此默认第 0 个元素为 0。例如悬崖 [1,1,4,5,1,4] 的危险值为 $max(1-0 , 1-1 , 4-1 , 5-4 , 1-5 , 4-1) = max(1 , 0 , 3 , 1 , -4 , 3) = 3$。

现在嘤嘤需要为小沙生成一座悬崖，其中每个高度对应的突出度 $a_i$ 都可以在 $[l_i,r_i]$ 中选择一个整数。由于嘤嘤**非常善良**，决定使生成的这个悬崖的危险值尽可能大，你能帮帮嘤嘤吗？

Format

Input

第一行输入一个整数 $n(1 \leq n \leq 10^5)$ 表示悬崖的高度。

接下来 $n$ 行，每行输入两个整数 $l_i,r_i(-10^9 \leq l_i \leq r_i \leq 10^9)$ 。

Output

输出一个整数。

Samples

2
1 1
2 2

1

Limitation

1s, 1024KiB for each test case.