โจทย์ปัญหา

หอคอย JOIOI คือเกมสำหรับเล่น $1$ คนโดยใช้จานกลม

เกมนี้เล่นโดยใช้จานกลมจำนวนหนึ่ง ซึ่งแต่ละใบมีตัวอักษรตัวใดตัวหนึ่งจาก J, O หรือ I เขียนอยู่ จานกลมแต่ละใบมีเส้นผ่านศูนย์กลางแตกต่างกันทั้งหมด และเมื่อเริ่มเกม จานกลมเหล่านี้จะถูกวางซ้อนกันจากล่างขึ้นบนเรียงตามลำดับเส้นผ่านศูนย์กลางจากใหญ่ไปเล็ก คุณต้องการใช้จานกลมเหล่านี้เพื่อสร้างหอคอยมินิ JOIOI ให้ได้มากที่สุดเท่าที่จะเป็นไปได้ หอคอยมินิ JOIOI ประกอบด้วยจานกลม $3$ ใบ ซึ่งเมื่ออ่านเรียงตามลำดับเส้นผ่านศูนย์กลางของจานกลมจากเล็กไปใหญ่แล้วจะอ่านได้เป็น JOI หรือ IOI อย่างไรก็ตาม ไม่สามารถใช้จานกลมใบเดิมซ้ำตั้งแต่ $2$ ครั้งขึ้นไปได้

รูปภาพ: จาก JOIOII สามารถสร้างหอคอยมินิ JOIOI ได้ $2$ หอ

งานของคุณ

ตัวอักษรที่เขียนอยู่บนจานกลมที่เตรียมไว้จะถูกกำหนดให้เป็นสตริง $S$ ความยาว $N$ เรียงตามลำดับเส้นผ่านศูนย์กลางของจานกลมจากเล็กไปใหญ่ จงเขียนโปรแกรมเพื่อหาค่ามากที่สุดของจำนวนหอคอยมินิ JOIOI ที่สามารถสร้างได้โดยใช้จานกลมเหล่านี้

ขอบเขต

• $1 \le N \le 1000000$: ความยาวของสตริง $S$

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน

• ในบรรทัดที่ $1$ มีจำนวนเต็ม $N$ เขียนอยู่ โดย $N$ แทนความยาวของสตริง $S$
• ในบรรทัดที่ $2$ มีสตริง $S$ เขียนอยู่

ข้อมูลส่งออก

พิมพ์ออกทางเอาต์พุตมาตรฐานเป็นจำนวนเต็มใน $1$ บรรทัด ที่แทนค่ามากที่สุดของจำนวนหอคอยมินิ JOIOI ที่สามารถสร้างได้

เกณฑ์การให้คะแนน

• สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $10\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $N \le 15$
• สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $30\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $N \le 50$
• สำหรับข้อมูลที่ใช้ตรวจให้คะแนน คิดเป็น $50\%$ ของคะแนนทั้งหมด จะสอดคล้องกับ $N \le 3000$

ตัวอย่าง 1

ข้อมูลนำเข้า

6
JOIIOI

ข้อมูลส่งออก

2

JOIIOI มี JOI และ IOI เป็นลำดับย่อยอย่างละ $1$ ตัว ดังนั้นจึงสามารถสร้างหอคอยมินิ JOIOI ได้ $2$ หอ

ตัวอย่าง 2

ข้อมูลนำเข้า

5
JOIOI

ข้อมูลส่งออก

1

แม้ว่าจะมี JOI และ IOI เป็นลำดับย่อย แต่เนื่องจากไม่สามารถใช้ตัวอักษรตัวเดิมซ้ำตั้งแต่ $2$ ครั้งขึ้นไปได้ จึงไม่สามารถดึงออกมาพร้อมกันได้

ตัวอย่าง 3

ข้อมูลนำเข้า

6
JOIOII

ข้อมูลส่งออก

2

ตัวอย่างนี้ตรงกับตัวอย่างในโจทย์ปัญหา

ตัวอย่าง 4

ข้อมูลนำเข้า

15
JJOIIOOJOJIOIIO

ข้อมูลส่งออก

4