某通信系统持续记录二进制信号,每个信号包含:
该信号出现的精确的时间,该时间表示是从系统启动后的第几秒记录到的该信号,所有信号记录到的时间都是互不相同的。
信号值 0 或 1 。
工程师需要按时间从早到晚的顺序,从所有的信号中,找到一段连续的信号记录,要求该段记录中 0 和 1 的出现次数完全相等。定义信号的时间跨度为:这段连续信号记录最后信号出现的时间减去第一个信号出现的时间。
请你编程找出所有满足条件的记录段中,时间跨度最大的值。若不存在,返回 0。
第一行为整数 N,表示信号个数。
接下来为 N 行。每行两个数 a,b。a代表信号值,值为 0 或 1,b 代表信号出现的时间,用空格隔开。
输出满足条件的最大时间跨度。
6 1 100 0 105 1 108 0 112 1 115 0 120
20
7 0 11 1 10 1 25 1 12 1 4 0 13 1 22
11
5 1 10 1 9 1 8 1 7 1 6
0
从时刻 100 到 时刻 120,包含 3个 信号 1 和 3 个信号 0,出现次数相同,所以符合要求,最大时间跨度为 120 - 100 = 20。
对于 40\% 的数据,满足 1 \le N \le 1000。
对于 100\% 的数据,满足 1 \le N \le 50,000,0 \le b \le 10^9。