The largest beautiful picture
Time Limit : 1 Second
Memory Limit : 512 MB
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).
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)
The maximum size.
- sample input
5 8 W 11 S 3 W 10 W 5 S
- sample output