\(N\) con bò của Farmer John (\(2 \le N \le 100\,000\)) đang đứng tại nhiều vị trí khác nhau dọc theo một hàng rào dài một chiều. Con bò thứ \(i\) đứng tại vị trí \(x_i\) (một số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\,000\)) và là bò trắng trơn hoặc bò đốm. Không có hai con bò nào đứng cùng một vị trí, và có ít nhất một con bò trắng.

Farmer John muốn chụp ảnh một đoạn liên tiếp gồm các con bò để mang đến hội chợ hạt. Để công bằng với những con bò khác nhau của mình, ông muốn trong ảnh có số bò trắng bằng số bò đốm. Farmer John muốn xác định kích thước lớn nhất của một bức ảnh công bằng như vậy, trong đó kích thước của bức ảnh là hiệu giữa vị trí lớn nhất và vị trí nhỏ nhất của các con bò trong ảnh.

Để có cơ hội chụp được một bức ảnh lớn hơn nữa, Farmer John mang theo một thùng sơn và có thể tùy ý chọn một tập con các con bò trắng để sơn đốm lên chúng, qua đó biến chúng thành bò đốm. Hãy xác định kích thước lớn nhất của một bức ảnh công bằng mà Farmer John có thể chụp khi ông được phép sơn một số con bò trắng; tất nhiên, nếu thấy tốt hơn thì ông không cần sơn con nào.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(x_i\) và ký tự W nếu đó là bò trắng hoặc S nếu đó là bò đốm.

Ràng buộc

• \(2 \le N \le 100\,000\).
• \(0 \le x_i \le 1\,000\,000\,000\).
• Không có hai con bò nào đứng cùng một vị trí.
• Có ít nhất một con bò trắng.

Dữ liệu ra

• In ra kích thước lớn nhất của một bức ảnh công bằng mà Farmer John có thể chụp sau khi có thể đã sơn một số con bò trắng thành bò đốm.

Ví dụ

5
8 W
11 S
3 W
10 W
5 S

7

Nguồn

USACO 2014 US Open, Silver — Problem 1: Fair Photography

Tác giả đề: Brian Dean, 2014.