Farmer John's N cows (1 <= N <= 100,000) are standing at various positions along a long one-dimensional fence. The ith cow is standing at position x_i (an integer in the range 0...1,000,000,000) and has breed b_i (either 'G' for Guernsey or 'H' for Holstein). No two cows occupy the same position.

FJ wants to take a photo of a contiguous interval of cows, but he wants all of his breeds to be fairly represented. Therefore, he wants to ensure that, for whatever breeds are present in the photo, there is an equal number of each breed (a photo with all Holsteins is ok, a photo with 27 Holsteins and 27 Guernseys is ok, but a photo with 10 Holsteins and 9 Guernseys is not). Help FJ by finding the maximum size of a photo that satisfies his constraints. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo. A photo of just a single cow has size zero.

Line 1: The integer N.

Lines 2..1+N: Line i+1 contains x_i and b_i.

A single integer indicating the maximum size of a fair photo.

riseoj 작성

출처 올림피아드 > USACO > 2013-2014 > US Open > Bronze