بيان المسألة

برج 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