Phố mua sắm JOI có \(N\) cửa hàng dọc theo một đại lộ một chiều, đánh số từ 1 đến \(N\) theo hướng từ lối vào tới lối ra. Mỗi cửa hàng đã chọn một con dấu J, O hoặc I.

Người tham gia cuộc sưu tập dấu vào đúng ba cửa hàng theo thứ tự trên phố. Nếu ba dấu trên thẻ lần lượt là J, O, I, họ nhận được phiếu quà tặng.

Một cửa hàng mới sẽ được mở tại một trong \(N+1\) vị trí: trước cửa hàng 1, giữa hai cửa hàng liên tiếp, hoặc sau cửa hàng \(N\). Cửa hàng mới cũng chọn một trong ba con dấu. Hãy chọn vị trí và con dấu để tối đa hóa số bộ ba cửa hàng mang lại phiếu quà tặng.

Dữ liệu vào

• Dòng 1 chứa \(N\).
• Dòng 2 chứa xâu \(S\) dài \(N\), chỉ gồm J, O, I; ký tự thứ \(i\) là dấu của cửa hàng \(i\).

Dữ liệu ra

In ra số bộ ba lớn nhất. Kết quả có thể vượt miền số nguyên có dấu 32 bit.

Ràng buộc

Phân nhóm

• Nhóm 1 (30 điểm): \(N\le200\).
• Nhóm 2 (20 điểm): \(N\le3000\).
• Nhóm 3 (50 điểm): không có ràng buộc bổ sung.

Ví dụ

5
JOIOI

6

7
JJJOIII

18

4
OIIJ

2

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 2.