โจทย์ปัญหา
ระหว่างที่คุณกำลังฝึกเขียนโปรแกรมเพื่อเตรียมตัวสำหรับการแข่งขัน JOI รอบชิงชนะเลิศ คุณสังเกตเห็นว่าโจทย์ในรอบคัดเลือกของ JOI ปีนี้มีแต่โจทย์เกี่ยวกับตัวเลขและไม่มีโจทย์เกี่ยวกับสตริงเลย ดังนั้นคุณจึงตัดสินใจแอบฝึกฝนโจทย์เกี่ยวกับสตริงให้เก่งขึ้นเพื่อทิ้งห่างคู่แข่ง เมื่อดูโจทย์ JOI ในอดีต คุณพบว่าควรทำความคุ้นเคยกับสตริงที่ประกอบด้วยอักขระ $3$ ชนิดคือ J, O และ I ลองมาพิจารณาสตริงเหล่านี้กัน คุณคิดโจทย์ว่า "จงตอบว่าสตริงที่กำหนดให้มี JOI เป็นสตริงย่อยหรือไม่" ซึ่งคุณก็แก้ได้ในทันที เพราะต้องการแก้โจทย์ที่มีระดับสูงขึ้น คุณจึงสร้างโจทย์ต่อไปนี้ขึ้นมา
สตริง $t$ เป็นสตริงย่อยของสตริง $s$ ถ้าสามารถสร้าง $s$ ได้โดยการเติมอักขระจำนวนหนึ่ง (อาจเป็น $0$ ตัวก็ได้) ที่จุดเริ่มต้นและจุดสิ้นสุดของ $t$ ตัวอย่างเช่น JJOOII เป็นสตริงย่อยของ OJJOOIIOJOI ในทางกลับกัน JOI ไม่ใช่สตริงย่อยของ JOOI
นอกจากนี้ สำหรับจำนวนเต็ม $k$ ที่มากกว่าหรือเท่ากับ $0$ สตริง JOI ระดับ $k$ คือสตริงที่เกิดจากการเรียงอักขระ J จำนวน $k$ ตัว, อักขระ O จำนวน $k$ ตัว และอักขระ I จำนวน $k$ ตัว ตามลำดับนี้ ตัวอย่างเช่น JJOOII เป็นสตริง JOI ระดับ $2$
เราต้องการหาสตริงที่มีระดับมากที่สุดในบรรดาสตริง JOI ที่เป็นสตริงย่อยของสตริงที่กำหนดให้
งานของคุณ
กำหนดสตริง $S$ ความยาว $N$ ที่ประกอบด้วยอักขระ $3$ ชนิดคือ J, O และ I จงเขียนโปรแกรมเพื่อหาค่ามากที่สุดของ $k$ ที่ทำให้สตริง JOI ระดับ $k$ เป็นสตริงย่อยของ $S$
ขอบเขต
- $1 \le N \le 1000000 \ (= 10^6)$: ความยาวของ $S$
ข้อมูลนำเข้า
อ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน
- ในบรรทัดที่ $1$ มีสตริง $S$ ที่ประกอบด้วยอักขระ $3$ ชนิดคือ
J,OและIเขียนอยู่
ข้อมูลส่งออก
พิมพ์ออกทางเอาต์พุตมาตรฐานเป็นจำนวนเต็มใน $1$ บรรทัด ที่แทนค่ามากที่สุดของ $k$ ที่ทำให้สตริง JOI ระดับ $k$ เป็นสตริงย่อยของ $S$
เกณฑ์การให้คะแนน
- สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $20\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $N \le 100$
ตัวอย่าง 1
ข้อมูลนำเข้า
OJJOOIIOJOI
ข้อมูลส่งออก
2
OJJOOIIOJOI มี JJOOII ซึ่งเป็นสตริง JOI ระดับ $2$ เป็นสตริงย่อย และไม่มีสตริง JOI ระดับ $3$ ขึ้นไปเป็นสตริงย่อย
ตัวอย่าง 2
ข้อมูลนำเข้า
IJJIIJJJ
ข้อมูลส่งออก
0
สตริง JOI ระดับ $0$ คือสตริงที่มีความยาว $0$
ตัวอย่าง 3
ข้อมูลนำเข้า
JOIJOIJOIJOIJOI
ข้อมูลส่งออก
1
ตัวอย่าง 4
ข้อมูลนำเข้า
OOJJJJJJOOOOIIIII
ข้อมูลส่งออก
4