HUST 2016招新选拔

From: 2016-03-06 14:00:00 To: 2016-03-06 17:30:00 Now: 2017-09-24 21:45:40 Status: Public

C - The largest beautiful picture

Time Limit: 1s Memory Limit: 512MB

Submissions: 23 Solved: 1
Description

    Farmer John has N cows.They stands at different points along a fence.The ith cow, which is either a white cow or a spotted cow, stands at X[i].

    Farmer John wants to photo his cows, and when the number of white cows in the photo is equal to the number of spotted cows in the photo, he regards the photo as a beautiful picture.Farmer John wants to get a beautiful picture with maximum size, where the size of photo is determined by the max(X[i]) minus the min(X[i])

    To take larger photo, Farmer John decides to paint spots on some white cows to turn them into spotted cows.(he can also take photos without painting any of white cows).

Input

The first line is an integer N(2<=N<=100,000)

The 2..N+1 lines:Line i+1 contains an integers X[i] and either W(white) or S(spotted).

(X[i] != X[j], if i != j; 0<=X[i]<=1,000,000,000)

Output

The maximum size.

Sample Input
5
8 W
11 S
3 W
10 W
5 S
Sample Output
7
Hint
Source