Lýsing á verkefni

JOIOI-turninn er leikur fyrir $1$ leikmann sem spilaður er með skífum.

Þessi leikur er spilaður með nokkrum skífum þar sem á hverja skífu er skrifaður einn af stöfunum J, O eða I. Skífurnar hafa innbyrðis ólík þvermál og í upphafi leiksins er þessum skífum staflað neðan frá og upp í lækkandi röð eftir þvermáli. Með því að nota þessar skífur viltu búa til eins marga smá-JOIOI-turna og mögulegt er. Smá-JOIOI-turn samanstendur af $3$ skífum og lesinn í hækkandi röð eftir þvermáli skífanna stendur JOI eða IOI. Hins vegar má ekki nota sömu skífuna $2$ sinnum eða oftar.

Mynd: Úr JOIOII er hægt að búa til $2$ smá-JOIOI-turna

Verkefni

Stafirnir sem skrifaðir eru á tilbúnu skífurnar eru gefnir í hækkandi röð eftir þvermáli skífanna sem strengur $S$ af lengd $N$. Skrifaðu forrit til að finna hæsta gildið á fjölda smá-JOIOI-turna sem hægt er að búa til með þessum skífum.

Takmarkanir

• $1 \le N \le 1000000$: Lengdin á strengnum $S$.

Inntak

Lestu eftirfarandi gögn úr staðalinntaki.

• Á $1$. línu er skrifuð heiltala $N$. $N$ táknar lengd strengsins $S$.
• Á $2$. línu er skrifaður strengur $S$.

Úttak

Skrifaðu út í staðalúttak á $1$ línu heiltölu sem táknar hæsta gildið á fjölda smá-JOIOI-turna sem hægt er að búa til.

Undirverkefni

• Fyrir $10\%$ stiga í prófunargögnum gildir $N \le 15$.
• Fyrir $30\%$ stiga í prófunargögnum gildir $N \le 50$.
• Fyrir $50\%$ stiga í prófunargögnum gildir $N \le 3000$.

Dæmi 1

Inntak

6
JOIIOI

Úttak

2

JOIIOI inniheldur JOI og IOI sem hlutrunur $1$ sinni hvora, þannig að fjöldi smá-JOIOI-turna sem hægt er að búa til er $2$.

Dæmi 2

Inntak

5
JOIOI

Úttak

1

Þótt strengurinn innihaldi JOI og IOI sem hlutrunur, þá er ekki hægt að nota staf $2$ sinnum eða oftar, svo ekki er hægt að taka þær út samtímis.

Dæmi 3

Inntak

6
JOIOII

Úttak

2

Þetta dæmi samsvarar dæminu í verkefnalýsingunni.

Dæmi 4

Inntak

15
JJOIIOOJOJIOIIO

Úttak

4