Есептің шарты

JOIOI мұнарасы — дискілерді пайдаланып $1$ адам ойнайтын ойын.

Бұл ойын әрқайсысында J, O, I таңбаларының бірі жазылған бірнеше дискіні пайдаланып ойналады. Дискілердің диаметрлері өзара әртүрлі, және ойын басталған кезде бұл дискілер диаметрлерінің кему ретімен астынан үстіне қарай жиналып тұрады. Сіз осы дискілерді пайдаланып, мүмкіндігінше көп мини JOIOI мұнараларын жасағыңыз келеді. Мини JOIOI мұнарасы $3$ дискіден тұрады және дискілердің диаметрінің өсу ретімен оқығанда JOI немесе IOI деп оқылады. Алайда, бір дискіні $2$ немесе одан көп рет пайдалануға болмайды.

Сурет: JOIOII жолынан $2$ мини JOIOI мұнарасын жасауға болады

Тапсырма

Дайындалған дискілерде жазылған таңбалар дискілердің диаметрінің өсу ретімен ұзындығы $N$ болатын $S$ жолы ретінде беріледі. Осы дискілерді пайдаланып жасауға болатын мини 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