1920W023 - Lớp học múa
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: admin

Lớp học múa khiêu vũ dạ hội của giáo sư Padegras có n học sinh nam và nữ ghi tên. Giáo sư cho tất cả học sinh xếp thành một hàng dọc và chọn một nhóm các học sinh liên tiếp nhau cho buổi học đầu tiên với yêu cầu là số học sinh nam và nữ phải bằng nhau.

Hãy xác định, giáo sư Padegras có bao nhiêu cách lựa chọn khác nhau cho buổi học đầu tiên.

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên n (1 ≤ n ≤ 106),
  • Dòng thứ 2 chứa xâu độ dài n bao gồm các ký tự từ tập {a, b} xác định dòng xếp hàng, a là nam, b – nữ.

Kết quả

  • Ghi một số nguyên duy nhất là số cách lựa chọn của giáo sư Padegras.

Ví dụ

Input

8
abbababa

Output

13

Giới hạn

  • 20% số test đầu tiên có n≤100 
  • 30%  số test tiếp theo có 10^2<n≤10^3
  • 50% số test cuối: Không có ràng buộc gì thêm.

Nguồn: Nhóm contest 10 - 2019-2020

Back to Top