题目描述

Farmer John 决定给他的奶牛们照一张合影，他让 $N$ ($1 \leq N \leq 50,000$) 头奶牛站成一条直线，每头牛都有它的坐标$x$($0 \leq x \leq 10^9$)和种族($0$或$1$)。

他只给一部分牛照相，并且这一组牛的阵容必须是“平衡的”。

平衡的阵容，指的是在一组牛中，种族$0$和种族$1$的牛的数量相等。

区间的大小为区间内最右边的牛的坐标减去最左边的牛的坐标。

请算出最广阔的区间，使这个区间内的牛阵容平衡。

输入

第一行为$n$，接下来为$n$行。

每行两个数$a,b$,$a$为$0$或者$1$，为种族，$b$为坐标$x$。

输出

输出平衡的最大区间。

样例

样例输入1

7
0 11
1 10
1 25
1 12
1 4
0 13
1 22

样例输出1

11