Đề bài

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

Trò chơi này được thực hiện bằng cách sử dụng một số đĩa tròn, mỗi đĩa có ghi một trong các ký tự J, O hoặc I. Các đĩa có đường kính đôi một khác nhau, và khi bắt đầu trò chơi, các đĩa này được xếp chồng từ dưới lên trên theo thứ tự đường kính giảm dần. Sử dụng các đĩa này, bạn muốn tạo ra càng nhiều tháp JOIOI mini càng tốt. Một tháp JOIOI mini gồm $3$ đĩa, và khi đọc theo thứ tự đường kính đĩa tăng dần thì đọc được là JOI hoặc IOI. Tuy nhiên, không được sử dụng cùng một đĩa từ $2$ lần trở lên.

Hình: Từ JOIOII có thể tạo được $2$ tháp JOIOI mini

Nhiệm vụ

Các ký tự ghi trên các đĩa đã chuẩn bị được cho dưới dạng một xâu $S$ độ dài $N$ theo thứ tự đường kính đĩa tăng dần. Hãy viết chương trình tìm giá trị lớn nhất của số lượng tháp JOIOI mini có thể tạo được bằng cách sử dụng các đĩa này.

Giới hạn

• $1 \le N \le 1000000$: Độ dài của xâu $S$.

Dữ liệu vào

Đọc dữ liệu sau từ đầu vào chuẩn.

• Ở dòng thứ $1$, ghi số nguyên $N$. $N$ biểu thị độ dài của xâu $S$.
• Ở dòng thứ $2$, ghi xâu $S$.

Kết quả

In ra đầu ra chuẩn trên $1$ dòng một số nguyên biểu thị giá trị lớn nhất của số lượng tháp JOIOI mini có thể tạo được.

Tiêu chí chấm điểm

• Trong dữ liệu chấm điểm, $10\%$ số điểm thỏa mãn $N \le 15$.
• Trong dữ liệu chấm điểm, $30\%$ số điểm thỏa mãn $N \le 50$.
• Trong dữ liệu chấm điểm, $50\%$ số điểm thỏa mãn $N \le 3000$.

Ví dụ 1

Đầu vào

6
JOIIOI

Đầu ra

2

JOIIOI chứa JOI và IOI mỗi xâu $1$ lần dưới dạng dãy con, nên số tháp JOIOI mini có thể tạo được là $2$.

Ví dụ 2

Đầu vào

5
JOIOI

Đầu ra

1

Tuy chứa cả JOI và IOI dưới dạng dãy con, nhưng vì không thể sử dụng một ký tự từ $2$ lần trở lên nên không thể lấy ra đồng thời.

Ví dụ 3

Đầu vào

6
JOIOII

Đầu ra

2

Ví dụ này tương ứng với ví dụ trong đề bài.

Ví dụ 4

Đầu vào

15
JJOIIOOJOJIOIIO

Đầu ra

4