بيان المسألة
أثناء تدربك على البرمجة استعدادًا للجولة النهائية من 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