Balanced Lineup

Interview

Time limit2sMemory limit256 MB

Summary
Given fans sorted by x-coordinate with a gender bit each, find the longest contiguous segment that has an equal number of men and women.
Level

Medium5 of 10

Topics
Prefix sum, Hash map, Sorting, Array
Solved
No attempts yet

Problem

Fans stand in one line at distinct x-coordinates. You may choose a group consisting of consecutive people in this line. A group is balanced if it contains the same number of men and women.

The length of a group is the difference between the smallest and largest x-coordinate in that group. Find the maximum length among all balanced groups.

Input

The first line contains the number of fans N (1 ≤ N ≤ 1,000,000).

Each of the next N lines contains a gender value and an x-coordinate, separated by a space. Gender is given as 0 for a man and 1 for a woman. Each x-coordinate is between 0 and 1,000,000,000 inclusive, and no two fans stand at the same x-coordinate. At least one fan of each gender exists.

Output

Print the length of the longest group satisfying the condition.

Examples1

  1. Example 1

    Input
    7
0 11
1 10
1 25
1 12
1 4
0 13
1 22
    Expected output
    11