Farmer John vừa mua thêm \(N\) con bò mới (\(3 \le N \le 5 \times 10^5\)), mỗi con thuộc giống Guernsey hoặc Holstein.

Các con bò hiện đang đứng thành một hàng, và Farmer John muốn chụp ảnh mọi dãy gồm ít nhất ba con bò liên tiếp. Tuy nhiên, ông không muốn chụp một bức ảnh có đúng một con bò giống Guernsey hoặc đúng một con bò giống Holstein — ông cho rằng con bò đơn độc ấy sẽ cảm thấy bị cô lập và ngượng ngùng. Sau khi chụp ảnh mọi dãy gồm ít nhất ba con bò, ông loại bỏ tất cả những bức ảnh được gọi là "cô đơn" này, tức các ảnh có đúng một con Guernsey hoặc đúng một con Holstein.

Cho biết thứ tự các con bò trong hàng, hãy giúp Farmer John xác định số bức ảnh cô đơn mà ông sẽ loại bỏ. Hai bức ảnh được coi là khác nhau nếu chúng bắt đầu hoặc kết thúc tại những con bò khác nhau trong hàng.

Dữ liệu vào

Dòng đầu tiên chứa \(N\).

Dòng thứ hai chứa một xâu gồm \(N\) ký tự. Ký tự thứ \(i\) là G nếu con bò thứ \(i\) trong hàng là Guernsey. Nếu không, ký tự đó là H và con bò thứ \(i\) là Holstein.

Dữ liệu ra

In ra số bức ảnh Farmer John sẽ loại bỏ vì chúng cô đơn.

Phân nhóm

• Dữ liệu 2–4: \(N \le 50\).
• Dữ liệu 5–10: \(N \le 5000\).
• Dữ liệu 11: Không có ràng buộc bổ sung. Lưu ý rằng đáp án của dữ liệu này có thể quá lớn để lưu trong kiểu số nguyên 32 bit tiêu chuẩn và có thể cần kiểu số nguyên lớn hơn (chẳng hạn kiểu long long int 64 bit trong C++).

Ví dụ

5
GHGHG

3

Nguồn

USACO 2021 December Contest, Bronze — Lonely Photo. Tác giả: Nick Wu.

https://usaco.org/index.php?page=viewproblem2&cpid=1155