Đề bài
Khi đang luyện tập lập trình cho Vòng Chung kết JOI, bạn nhận thấy rằng Vòng Sơ loại JOI năm nay chỉ toàn các bài toán số học chứ không có bài toán xâu ký tự nào. Vì vậy, bạn quyết định âm thầm rèn luyện kỹ năng giải các bài toán xâu ký tự để vượt lên trên các đối thủ. Xem lại các đề JOI trước đây, bạn nhận ra mình cần làm quen với các xâu chỉ gồm $3$ loại ký tự J, O và I. Hãy cùng xét những xâu như vậy. Bạn đã nghĩ ra bài toán "Cho biết một xâu cho trước có chứa JOI làm xâu con hay không", và giải được ngay lập tức. Muốn giải một bài toán ở cấp độ cao hơn, bạn đã tạo ra bài toán sau đây.
Xâu $t$ được gọi là xâu con của xâu $s$ nếu ta có thể thu được $s$ bằng cách thêm một số ký tự (cũng có thể là $0$ ký tự) vào đầu và cuối của $t$. Ví dụ, JJOOII là một xâu con của OJJOOIIOJOI. Mặt khác, JOI không phải là xâu con của JOOI.
Ngoài ra, với một số nguyên $k$ lớn hơn hoặc bằng $0$, xâu JOI cấp độ $k$ là xâu được tạo thành bằng cách xếp $k$ ký tự J, $k$ ký tự O và $k$ ký tự I theo đúng thứ tự đó. Ví dụ, JJOOII là xâu JOI cấp độ $2$.
Ta muốn tìm xâu có cấp độ lớn nhất trong số các xâu JOI là xâu con của xâu đã cho.
Nhiệm vụ
Cho một xâu $S$ có độ dài $N$ gồm $3$ loại ký tự J, O và I, hãy viết chương trình tìm giá trị lớn nhất của $k$ sao cho xâu JOI cấp độ $k$ là xâu con của $S$.
Giới hạn
- $1 \le N \le 1000000 \ (= 10^6)$: Độ dài của $S$.
Dữ liệu vào
Đọc dữ liệu sau từ đầu vào chuẩn.
- Ở dòng thứ $1$, ghi một xâu $S$ gồm $3$ loại ký tự
J,OvàI.
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 $k$ sao cho xâu JOI cấp độ $k$ là xâu con của $S$.
Tiêu chí chấm điểm
- Trong dữ liệu chấm điểm, $20\%$ số điểm thỏa mãn $N \le 100$.
Ví dụ 1
Đầu vào
OJJOOIIOJOI
Đầu ra
2
OJJOOIIOJOI chứa JJOOII, tức là xâu JOI cấp độ $2$, làm xâu con, và không chứa bất kỳ xâu JOI nào có cấp độ từ $3$ trở lên làm xâu con.
Ví dụ 2
Đầu vào
IJJIIJJJ
Đầu ra
0
Xâu JOI cấp độ $0$ là xâu có độ dài $0$.
Ví dụ 3
Đầu vào
JOIJOIJOIJOIJOI
Đầu ra
1
Ví dụ 4
Đầu vào
OOJJJJJJOOOOIIIII
Đầu ra
4