1373_Balancedlineup

Farmer John has decided to take a family portrait of some (maybe all) of the cows. In order to take the portrait, FJ has arranged all N ( 1 ≤ N ≤ 50,000 ) cows in a straight line. Each cow is labeled with its x coordinate ( range: 0..1,000,000,000 ) on the line as well as its breed (0 or 1).

Over the years, FJ has done some crazy things, and this activity is no exception. He will only photograph one group of cows, and that group must be "balanced". A contiguous group of cows is "balanced" if it contains the same number of cows from each of the two breeds.

Determine the widest expanse of cows that might have to fit in one photograph. The length of a balanced group is the difference in x values between the left-most and right-most cows in the group.

At least one cow of each breed appears in the input, and no two cows share the same x coordinate.

* Line 1: A single integer: N

* Lines 2..N+1: Each line contains two space-separated integers that describe a single cow containing respectively: a breed ID and an x coordinate

Line 1: A single integer specifying the size of the largest contiguous balanced group of cows.

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

11

Cows #1 (at 11), #4 (at 12), #6 (at 13), and #7 (at 22) form a contiguous balanced group occupying 22-11=11 units of length on the number line:

                                 <-------- balanced group -------->
            1                 1  0  1  0                          1        1
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25