题目描述

记录仪共记录了 $n$ 个信号。每个信号包含一个信号值和一个记录时间，信号值只可能是 $0$ 或 $1$，所有记录时间互不相同。

将记录按时间从早到晚排列后，请找出一段连续的记录，使其中信号值为 $0$ 和信号值为 $1$ 的记录数量相同。

一段记录的时间跨度等于其中最晚记录时间与最早记录时间之差。请输出符合要求的记录段的最大时间跨度。

输入格式

第一行包含一个整数 $n$。

接下来 $n$ 行，每行包含两个整数 $v_i$ 和 $t_i$，分别表示信号值和记录时间。输入的记录不一定按时间排序。

输出格式

输出一个整数，表示最大的时间跨度。如果不存在符合要求的记录段，输出 $0$。

6
1 2
0 5
1 9
0 15
0 20
1 30

28

数据范围与提示

• $1 \le n \le 5\times10^4$
• $v_i\in\{0,1\}$
• $0 \le t_i \le 10^9$
• 所有 $t_i$ 互不相同