Trên một đường tròn có \(2N\) điểm được đánh số từ \(1\) đến \(2N\) theo chiều kim đồng hồ. Mỗi điểm có màu trắng hoặc đen; có đúng \(N\) điểm trắng và \(N\) điểm đen.

Ta sẽ vẽ \(N\) đoạn thẳng nối các điểm này sao cho:

• Mỗi điểm là đầu mút của đúng một đoạn thẳng.
• Mỗi đoạn thẳng nối một điểm trắng với một điểm đen.

Số cặp đoạn thẳng giao nhau trong \(N\) đoạn thẳng được gọi là số giao cắt. Cho thông tin về màu của các điểm, hãy tính số giao cắt lớn nhất có thể đạt được khi vẽ \(N\) đoạn thẳng thỏa mãn các điều kiện trên.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\).
• Dòng thứ hai chứa xâu \(S\) có độ dài \(2N\), mô tả màu của các điểm. Mỗi ký tự của \(S\) là B hoặc W. Ký tự thứ \(i\) (\(1 \le i \le 2N\)) là B nếu điểm thứ \(i\) màu đen, và là W nếu điểm đó màu trắng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số giao cắt lớn nhất có thể đạt được khi vẽ \(N\) đoạn thẳng thỏa mãn các điều kiện đã cho.

Ràng buộc

• \(1 \le N \le 200000\).
• \(S\) có độ dài \(2N\), chỉ gồm các ký tự B và W.
• Trong \(S\), ký tự B xuất hiện đúng \(N\) lần và ký tự W xuất hiện đúng \(N\) lần.

Phân nhóm

Mọi phân nhóm đều thỏa mãn toàn bộ ràng buộc ở trên.

1. 4 điểm: \(N \le 8\).
2. 21 điểm: \(N \le 300\).
3. 10 điểm: \(N \le 2000\).
4. 65 điểm: Không có ràng buộc bổ sung.

Ví dụ

3
BBWWBW

2

5
BWBWBBWBWW

8

10
WBBBWBBWWBWWBWWBWBWB

41

16
WWWBWBBBBWWBWWBWWBBWWBBBWBBBWWBW

105

Nguồn

JOI Open Contest 2020, bài 2. Bản dịch từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản (JCIOI), theo giấy phép CC BY-SA 4.0.