題目描述

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