題目描述

JOIOI 之塔係一個用圓盤玩嘅單人遊戲。

呢個遊戲用若干個圓盤進行，每個圓盤上面都寫有 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 各自包含 $1$ 個 JOI 同埋 IOI 作為子序列，所以可以整出 $2$ 座迷你 JOIOI 之塔。

樣例 2

輸入

5
JOIOI

輸出

1

雖然包含 JOI 同埋 IOI 作為子序列，但係因為同一個字元唔可以用 $2$ 次或以上，所以唔可以同時拎出嚟。

樣例 3

輸入

6
JOIOII

輸出

2

呢個樣例對應題目描述入面嘅例子。

樣例 4

輸入

15
JJOIIOOJOJIOIIO

輸出

4