Kệ Trà Cân Bằng

Time limit: 1.0s Memory limit: 256M Read editorial

Problem

Ông Tư có một quán trà thảo mộc nhỏ tên là Ba Lá, nổi tiếng với ba loại trà đóng chai: trà Atiso, trà Bạc hà và trà Cúc. Ngoài ra quán còn bán đủ thứ đồ uống khác như nước sấu, nước mía, sữa đậu nành, ... Mỗi loại đồ uống được ông ký hiệu bằng một chữ cái in hoa: A, B, C là ba loại trà đặc biệt, các chữ cái còn lại là đồ uống khác.

Trên chiếc kệ dài trước quán, ông Tư xếp \(n\) chai thành một hàng ngang. Hàng chai được mô tả bởi một chuỗi \(s\) gồm \(n\) chữ cái in hoa, chữ cái thứ \(i\) là loại đồ uống của chai thứ \(i\) tính từ trái sang.

Tuần này ông Tư chạy chương trình "Combo Cân Bằng": khách được chọn một đoạn liên tiếp các chai trên kệ để mua với giá ưu đãi, miễn là đoạn đó cân bằng, tức là:

  • số chai trà Atiso, số chai trà Bạc hà và số chai trà Cúc trong đoạn bằng nhau, và
  • mỗi loại trong ba loại trà đó có ít nhất một chai.

Các chai đồ uống khác nằm trong đoạn không ảnh hưởng gì, khách vẫn được mua kèm.

Ông Tư tò mò không biết trên kệ hiện tại có bao nhiêu đoạn cân bằng. Hai đoạn được coi là khác nhau nếu vị trí bắt đầu hoặc vị trí kết thúc khác nhau. Kệ dài tới \(2 \times 10^5\) chai, ông đếm tay thì chắc đến Tết năm sau mới xong.

"Ba lá trà, mỗi lá một vị, đủ cả ba mới thành combo."

-- Ông Tư, chủ quán Ba Lá

Input

  • Dòng đầu tiên gồm một số nguyên \(n\) \((1 \leq n \leq 2 \times 10^5)\) là số chai trên kệ.
  • Dòng thứ hai gồm chuỗi \(s\) độ dài \(n\), chỉ gồm các chữ cái in hoa A-Z.

Output

  • In ra một số nguyên duy nhất là số đoạn cân bằng.

Sample

#InputOutput
1
6
ABCCBA
3
2
7
AXBYCZZ
3

Note

Đánh số các chai từ \(1\) đến \(n\).

Sample 1: có \(3\) đoạn cân bằng:

  • chai \(1\) đến \(3\): ABC;
  • chai \(4\) đến \(6\): CBA;
  • chai \(1\) đến \(6\): ABCCBA, mỗi loại trà có đúng \(2\) chai.

Sample 2: một đoạn cân bằng phải chứa đủ chai A (vị trí \(1\)), chai B (vị trí \(3\)) và chai C (vị trí \(5\)). Vậy đoạn phải bắt đầu ở chai \(1\) và kết thúc ở chai \(5\), \(6\) hoặc \(7\), tổng cộng \(3\) đoạn: AXBYC, AXBYCZ, AXBYCZZ.

Các đoạn như X hay ZZ có số chai mỗi loại trà đều bằng \(0\), nhưng không được tính vì không có chai trà nào.


Comments

There are no comments at the moment.

Code editor