Fair Photo

FJ has N cows (2 ≤ N ≤ 100,000) positioned along a one‐dimensional fence. The ith cow is at position \( x_i \) (an integer between 0 and 1,000,000,000) and is either a plain white cow or a spotted cow. No two cows share the same position, and there is at least one white cow.

FJ wants to take a photo of a contiguous interval of cows for the county fair. To be fair to his cows, he requires that the photo contains an equal number of white cows and spotted cows after he optionally uses a bucket of paint to turn some of his white cows into spotted cows. Formally, assume an interval contains W white cows and S spotted cows. FJ is allowed to paint any subset of white cows in that interval, so that if he paints exactly \( x \) white cows, the final counts become \( W-x \) white and \( S+x \) spotted. In order for the photo to be fair, these two numbers must be equal. It is easy to see that the interval can be made fair if and only if

[ W - x = S + x \quad\Longrightarrow\quad 2x = W - S \quad\text{with } 0 \le x \le W, ]

that is, \( W - S \) must be nonnegative and even.

The size of a photo is defined as the difference between the maximum and minimum cow positions in the interval. Please determine the largest size of a fair photo FJ can take given that he may paint some of his white cows.

inputFormat

The first line contains a single integer \( N \) (2 ≤ N ≤ 100,000). Each of the next \( N \) lines contains an integer \( x_i \) (0 ≤ \( x_i \) ≤ 1,000,000,000) and a character. The character is either W indicating a white cow or S indicating a spotted cow. It is guaranteed that no two cows share the same position and that there is at least one white cow.

outputFormat

Output a single integer, which is the maximum size (difference between the maximum and minimum positions) of a contiguous interval of cows that can be made fair by painting an appropriate subset of white cows.

sample

4
1 W
3 S
10 W
15 S

14