תיאור הבעיה

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

מחרוזת $t$ היא תת-מחרוזת של מחרוזת $s$ אם ניתן לקבל את $s$ על ידי הוספת מספר כלשהו של תווים (גם $0$ תווים מותר) לתחילתה ולסופה של $t$. לדוגמה, JJOOII היא תת-מחרוזת של OJJOOIIOJOI. לעומת זאת, JOI אינה תת-מחרוזת של JOOI.

כמו כן, עבור מספר שלם $k$ הגדול או שווה ל-$0$, מחרוזת-JOI מרמה $k$ היא מחרוזת הנוצרת מסידור של $k$ תווים J, $k$ תווים O ו-$k$ תווים I בסדר זה. לדוגמה, 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