Problembeskrivelse
Tårnet av JOIOI er et spill for $1$ spiller som spilles med skiver.
Dette spillet spilles med flere skiver, der hver skive har ett av tegnene J, O eller I skrevet på seg. Skivene har innbyrdes forskjellige diametere, og ved starten av spillet er disse skivene stablet nedenfra og opp i synkende rekkefølge etter diameter. Ved å bruke disse skivene ønsker du å lage så mange mini-JOIOI-tårn som mulig. Et mini-JOIOI-tårn består av $3$ skiver, og kan leses som JOI eller IOI når det leses i stigende rekkefølge etter skivenes diameter. Den samme skiven kan imidlertid ikke brukes $2$ eller flere ganger.
Figur: Fra JOIOII kan det lages $2$ mini-JOIOI-tårn
Oppgave
Tegnene som er skrevet på de klargjorte skivene, er gitt som en streng $S$ med lengde $N$ i stigende rekkefølge etter skivenes diameter. Skriv et program for å finne det maksimale antallet mini-JOIOI-tårn som kan lages ved å bruke disse skivene.
Begrensninger
- $1 \le N \le 1000000$: Lengden på strengen $S$.
Inndata
Les følgende data fra standard inndata.
- På den $1$. linjen står et heltall $N$. $N$ representerer lengden på strengen $S$.
- På den $2$. linjen står en streng $S$.
Utdata
Skriv ut på standard utdata på $1$ linje et heltall som representerer det maksimale antallet mini-JOIOI-tårn som kan lages.
Deloppgaver
- For $10\%$ av poengene i testdataene er $N \le 15$ oppfylt.
- For $30\%$ av poengene i testdataene er $N \le 50$ oppfylt.
- For $50\%$ av poengene i testdataene er $N \le 3000$ oppfylt.
Eksempel 1
Inndata
6 JOIIOI
Utdata
2
JOIIOI inneholder JOI og IOI som delsekvenser $1$ gang hver, så antallet mini-JOIOI-tårn som kan lages er $2$.
Eksempel 2
Inndata
5 JOIOI
Utdata
1
Selv om den inneholder JOI og IOI som delsekvenser, kan et tegn ikke brukes $2$ eller flere ganger, så de kan ikke tas ut samtidig.
Eksempel 3
Inndata
6 JOIOII
Utdata
2
Dette eksempelet tilsvarer eksempelet i problembeskrivelsen.
Eksempel 4
Inndata
15 JJOIIOOJOJIOIIO
Utdata
4