Fair Photography

Farmer John's $N$ cows ($1 \le N \le 100{,}000$) stand at distinct positions $x_i$ ($0 \le x_i \le 10^9$) along a long fence. Cow $i$ has breed $b_i$, either Guernsey G or Holstein H.

FJ wants a photo of a contiguous group of cows along the sorted line. Every breed that appears in the photo must appear the same number of times. A photo with only one breed is allowed.

Find the maximum size of a valid photo. The size is the difference between the largest and smallest positions among cows in the photo. A photo of a single cow has size $0$.

Line 1 contains $N$. Each of the next $N$ lines contains $x_i$ and $b_i$.

Print one integer, the maximum photo size.

After sorting by position, map G to $+1$ and H to $-1$. Equal prefix sums mark equal breed counts between two indices. Any contiguous block with only one breed is also valid. Take the maximum span from both cases.