תיאור הבעיה

מגדל JOIOI הוא משחק לשחקן $1$ המשוחק באמצעות דיסקיות.

משחק זה משוחק באמצעות מספר דיסקיות, שעל כל אחת מהן כתוב אחד התווים J, O או I. לדיסקיות יש קטרים שונים זה מזה, ובתחילת המשחק דיסקיות אלו מונחות זו על גבי זו מלמטה למעלה בסדר יורד של הקוטר. באמצעות הדיסקיות הללו, ברצונך ליצור כמה שיותר מיני-מגדלי JOIOI. מיני-מגדל JOIOI מורכב מ-$3$ דיסקיות, ונקרא כ-JOI או כ-IOI כאשר קוראים אותו בסדר עולה של קוטר הדיסקיות. עם זאת, לא ניתן להשתמש באותה דיסקית $2$ פעמים או יותר.

איור: מתוך JOIOII ניתן ליצור $2$ מיני-מגדלי JOIOI

משימה

התווים הכתובים על הדיסקיות שהוכנו נתונים כמחרוזת $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