\(N\) con bò của Farmer John (\(1 \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à thuộc giống \(b_i\) (G nếu là giống Guernsey hoặc H nếu là giống Holstein). Không có hai con bò nào đứng cùng một vị trí.

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, nhưng ông muốn tất cả các giống xuất hiện trong ảnh được đại diện một cách công bằng. Vì vậy, với những giống có mặt trong ảnh, ông muốn số bò của mỗi giống đều bằng nhau. Chẳng hạn, một bức ảnh chỉ có bò Holstein là hợp lệ; một bức ảnh có \(27\) bò Holstein và \(27\) bò Guernsey cũng hợp lệ; nhưng một bức ảnh có \(10\) bò Holstein và \(9\) bò Guernsey thì không hợp lệ.

Hãy giúp Farmer John chụp một bức ảnh công bằng bằng cách tìm kích thước lớn nhất của một bức ảnh thỏa mãn các điều kiện trên. 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. Farmer John có thể chỉ chụp một con bò; khi đó bức ảnh có kích thước bằng \(0\).

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à \(b_i\).

Ràng buộc

• \(1 \le N \le 100\,000\).
• \(0 \le x_i \le 1\,000\,000\,000\).
• \(b_i\) là G hoặc H.
• Không có hai con bò nào đứng cùng một vị trí.

Dữ liệu ra

• In ra một số nguyên duy nhất là kích thước lớn nhất của một bức ảnh công bằng.

Ví dụ

6
4 G
10 H
7 G
16 G
1 G
3 H

7

Nguồn

USACO 2014 US Open, Bronze — Problem 2: Fair Photography

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