Умова задачі

«Вежа 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