FJ's N cows (2 <= 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 is either a plain white cow or a spotted cow. No two cows occupy the same position, and there is at least one white cow.

FJ wants to take a photo of a contiguous interval of cows, ensuring there are equal numbers of white and spotted cows in the photo. The size of a photo is the difference between the maximum and minimum positions of the cows in the photo.

To give himself a better chance of a larger photo, FJ has a bucket of paint that he can use to paint spots on an arbitrary subset of his white cows, effectively turning them into spotted cows. Please determine the largest size of a fair photo FJ can take, given that he has the option of painting some of his white cows.

Line 1: The integer N.

Lines 2..1+N: Line i+1 contains x_i and either W (white cow) or S (spotted cow).

The maximum size of a fair photo FJ can take, after possibly painting some of his white cows to make them spotted.

riseoj 작성

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