4084 - 信号分析

题目描述

某通信系统持续记录二进制信号,每个信号包含:

  • 该信号出现的精确的时间,该时间表示是从系统启动后的第几秒记录到的该信号,所有信号记录到的时间都是互不相同的。

  • 信号值 01

工程师需要按时间从早到晚的顺序,从所有的信号中,找到一段连续的信号记录,要求该段记录中 01 的出现次数完全相等。定义信号的时间跨度为:这段连续信号记录最后信号出现的时间减去第一个信号出现的时间。

请你编程找出所有满足条件的记录段中,时间跨度最大的值。若不存在,返回 0

输入

第一行为整数 N,表示信号个数。

接下来为 N 行。每行两个数 a,ba代表信号值,值为 01b 代表信号出现的时间,用空格隔开。

输出

输出满足条件的最大时间跨度。

样例

输入

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
说明

样例 1 解释

从时刻 100 到 时刻 120,包含 3个 信号 13 个信号 0,出现次数相同,所以符合要求,最大时间跨度为 120 - 100 = 20

数据规模

对于 40\% 的数据,满足 1 \le N \le 1000

对于 100\% 的数据,满足 1 \le N \le 50,0000 \le b \le 10^9

标签
题目参数
时间限制 1 秒
内存限制 512 MB
提交次数 0
通过人数 0
金币数量 3 枚
难度 基础


上一题 下一题