Description

Farmer John 的 N 头牛正在数轴上吃草，第 i 头牛的坐标为 Xi。任意两头牛不会站在同一个位置吃草。

这些牛既有公牛，也有母牛。我们用 Si 表示第 i 头牛的性别，Si=0 表示母牛，Si=1 表示公牛。

John 要选出连续的一段牛去参加舞会。由于每头牛都需要一个异性舞伴，John 希望选出的这一段牛中公牛和母牛的数量相同。

John 并不希望选太多的牛。他希望牛们可以多留在数轴上吃草，这样可以给他干更多的活，或者产更多的奶。

但是，John 又希望他的牛们感觉他是一个很仁慈的主人。所以，John 想出了这样一个方案，他要选取长度最长的一段牛。一段牛的长度定义为该段中最右边的牛的坐标减去最左边的牛的坐标。当然，如果这样选出的牛的数量非常多，John 也无可奈何。

你能帮助他吗？你要保证选出的一段牛中公牛和母牛的数量相同，并且长度最长。

Input

第一行: 一个整数 N；

接下来 N 行: 每行两个整数 Si 和 Xi。Si ∈ {0, 1}，数据保证 Xi 互不相同。

Output

一个整数，表示能选出的最长的一段牛的长度。

Sample Input

7
0 0
0 1
1 2
1 3
1 10
1 100
0 200

Sample Output

100

Hint

20%：2 ≤ N ≤ 1,000

100%：2 ≤ N ≤ 100,000 ，Si ∈ {0, 1} ， 0 ≤ Xi ≤ 10^9