Tháp JOIOI là một trò chơi dành cho một người, sử dụng các đĩa.

Mỗi đĩa mang một trong ba chữ cái J, O, I. Đường kính của các đĩa đôi một khác nhau. Khi bắt đầu trò chơi, các đĩa được xếp chồng lên nhau, từ dưới lên trên theo thứ tự đường kính giảm dần.

Bạn muốn dùng các đĩa này để tạo ra nhiều tháp JOIOI nhỏ nhất có thể. Một tháp JOIOI nhỏ gồm \(3\) đĩa mà khi đọc các chữ cái theo thứ tự đường kính tăng dần, ta được JOI hoặc IOI. Không được sử dụng cùng một đĩa từ hai lần trở lên.

Yêu cầu

Các chữ cái trên những đĩa đã cho, đọc theo thứ tự đường kính tăng dần, được biểu diễn bằng xâu \(S\) có độ dài \(N\). Hãy viết chương trình tính số tháp JOIOI nhỏ nhiều nhất có thể tạo ra từ các đĩa này.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là độ dài của xâu \(S\).
• Dòng thứ hai chứa xâu \(S\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số tháp JOIOI nhỏ nhiều nhất có thể tạo ra.

Ràng buộc

• \(1\le N\le1000000\).
• \(S\) có độ dài \(N\) và chỉ gồm các ký tự J, O, I.

Phân nhóm

• \(10\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le15\).
• \(30\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le50\).
• \(50\%\) số điểm dành cho các dữ liệu thỏa mãn \(N\le3000\).

6
JOIIOI

2

JOIIOI chứa một dãy con JOI và một dãy con IOI, nên có thể tạo ra hai tháp JOIOI nhỏ.

5
JOIOI

1

Xâu chứa cả dãy con JOI lẫn dãy con IOI, nhưng không thể lấy đồng thời cả hai vì không được dùng một ký tự từ hai lần trở lên.

6
JOIOII

2

15
JJOIIOOJOJIOIIO

4