Deskripsi Masalah

Menara JOIOI adalah permainan $1$ pemain yang dimainkan menggunakan cakram.

Permainan ini dimainkan menggunakan beberapa cakram, yang masing-masing bertuliskan salah satu karakter dari J, O, atau I. Cakram-cakram tersebut memiliki diameter yang saling berbeda, dan pada awal permainan, cakram-cakram ini ditumpuk dari bawah ke atas dalam urutan diameter dari yang terbesar ke yang terkecil. Menggunakan cakram-cakram ini, Anda ingin membuat menara mini-JOIOI sebanyak mungkin. Sebuah menara mini-JOIOI terdiri dari $3$ cakram, dan terbaca JOI atau IOI ketika dibaca dalam urutan diameter cakram dari yang terkecil. Namun, cakram yang sama tidak dapat digunakan $2$ kali atau lebih.

Gambar: Dari JOIOII dapat dibuat $2$ menara mini-JOIOI

Tugas

Karakter-karakter yang tertulis pada cakram yang disiapkan diberikan sebagai sebuah string $S$ dengan panjang $N$ dalam urutan diameter cakram dari yang terkecil. Buatlah program untuk mencari nilai maksimum dari banyaknya menara mini-JOIOI yang dapat dibuat menggunakan cakram-cakram tersebut.

Batasan

• $1 \le N \le 1000000$: Panjang dari string $S$.

Masukan

Bacalah data berikut dari masukan standar.

• Pada baris ke-$1$, tertulis sebuah bilangan bulat $N$. $N$ menyatakan panjang dari string $S$.
• Pada baris ke-$2$, tertulis sebuah string $S$.

Keluaran

Keluarkan ke keluaran standar pada $1$ baris sebuah bilangan bulat yang menyatakan nilai maksimum dari banyaknya menara mini-JOIOI yang dapat dibuat.

Kriteria Penilaian

• Untuk $10\%$ dari poin pada data penilaian, dipenuhi $N \le 15$.
• Untuk $30\%$ dari poin pada data penilaian, dipenuhi $N \le 50$.
• Untuk $50\%$ dari poin pada data penilaian, dipenuhi $N \le 3000$.

Contoh 1

Masukan

6
JOIIOI

Keluaran

2

JOIIOI memuat JOI dan IOI masing-masing $1$ buah sebagai subbarisan, sehingga banyaknya menara mini-JOIOI yang dapat dibuat adalah $2$.

Contoh 2

Masukan

5
JOIOI

Keluaran

1

Meskipun memuat JOI dan IOI sebagai subbarisan, karena suatu karakter tidak dapat digunakan $2$ kali atau lebih, keduanya tidak dapat diambil secara bersamaan.

Contoh 3

Masukan

6
JOIOII

Keluaran

2

Contoh masukan/keluaran ini sesuai dengan contoh pada deskripsi masalah.

Contoh 4

Masukan

15
JJOIIOOJOJIOIIO

Keluaran

4