Условие задачи

«Башня JOIOI» — это игра для $1$ игрока, в которой используются диски.

В этой игре используется несколько дисков, на каждом из которых написан один из символов J, O или I. Диаметры всех дисков попарно различны, и в начале игры эти диски сложены в стопку снизу вверх в порядке убывания диаметра. Используя эти диски, вы хотите собрать как можно больше мини-башен JOIOI. Мини-башня JOIOI состоит из $3$ дисков, на которых при чтении в порядке возрастания диаметра дисков читается JOI или IOI. Однако один и тот же диск нельзя использовать $2$ или более раз.

Рисунок: Из JOIOII можно собрать $2$ мини-башни JOIOI

Задача

Символы, написанные на подготовленных дисках, заданы в порядке возрастания диаметра дисков в виде строки $S$ длины $N$. Напишите программу, которая находит максимальное количество мини-башен 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$ разу в качестве подпоследовательностей, поэтому можно собрать $2$ мини-башни JOIOI.

Пример 2

Ввод

5
JOIOI

Вывод

1

Хотя строка содержит JOI и IOI в качестве подпоследовательностей, один символ нельзя использовать $2$ или более раз, поэтому их нельзя выделить одновременно.

Пример 3

Ввод

6
JOIOII

Вывод

2

Этот пример соответствует примеру из условия задачи.

Пример 4

Ввод

15
JJOIIOOJOJIOIIO

Вывод

4