시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 154 53 36 34.286%

문제

JOIOI 탑은 원반을 이용해서 혼자 재미있게 놀 수 있는 게임이다.

이 게임은 J, O, I중 하나의 문자가 쓰여진 원반을 이용한다. 원반은 모두 반지름이 다르다. 가장 처음에 원반은 반지름이 큰 것이 가장 아래에 있고, 나머지는 작아지는 순서대로 쌓여 있다.

상근이는 이 원반을 이용해 가능한 많은 미니 JOIOI 탑을 만드려고 한다. 미니 JOIOI 탑은 3개의 원반으로 구성되며, 반지름이 작은 것부터 읽었을 때 JOI나 IOI이어야 한다. 한 미니 JOIOI 탑에 속한 원반은 다른 탑에 속할 수 없다.

반지름이 작은 원반부터 순서대로 원반에 적혀져 있는 문자가 순서대로 주어진다. 이때, 만들 수 있는 미니 JOIOI 탑의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 원반의 개수 N이 주어진다. 둘째 줄에는 원반에 적혀있는 문자가 반지름이 작은 순서대로 주어진다. (1 ≤ N ≤ 1,000,000)

출력

첫째 줄에 만들 수 있는 미니 JOIOI 탑의 최대 개수를 출력한다.

예제 입력 1

6
JOIIOI

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjU1MzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJKT0lPSSBcdWQwZDEiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdEpPSU9JIFx1ZDBkMVx1Yzc0MCBcdWM2ZDBcdWJjMThcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDYzY1x1Yzc5MCBcdWM3YWNcdWJiZjhcdWM3ODhcdWFjOGMgXHViMTgwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIEosIE8sIElcdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM0ZjBcdWM1ZWNcdWM5YzQgXHVjNmQwXHViYzE4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNmQwXHViYzE4XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzZkMFx1YmMxOFx1Yzc0MCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVkMDcwIFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwXHViMjk0IFx1Yzc5MVx1YzU0NFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjMzEzXHVjNWVjIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWM2ZDBcdWJjMThcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViYmY4XHViMmM4IEpPSU9JIFx1ZDBkMVx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiZjhcdWIyYzggSk9JT0kgXHVkMGQxXHVjNzQwIDNcdWFjMWNcdWM3NTggXHVjNmQwXHViYzE4XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YmE3MCwgXHViYzE4XHVjOWMwXHViOTg0XHVjNzc0IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWJkODBcdWQxMzAgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0YyBKT0lcdWIwOTggSU9JXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVkNTVjIFx1YmJmOFx1YjJjOCBKT0lPSSBcdWQwZDFcdWM1ZDAgXHVjMThkXHVkNTVjIFx1YzZkMFx1YmMxOFx1Yzc0MCBcdWIyZTRcdWI5NzggXHVkMGQxXHVjNWQwIFx1YzE4ZFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaW9pLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDM0OXB4OyBoZWlnaHQ6IDIxMHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVjNzkxXHVjNzQwIFx1YzZkMFx1YmMxOFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNmQwXHViYzE4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYmY4XHViMmM4IEpPSU9JIFx1ZDBkMVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWJjMThcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZkMFx1YmMxOFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVhYzAwIFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NCBcdWM3OTFcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYmY4XHViMmM4IEpPSU9JIFx1ZDBkMVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1NTMwIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JT0kgXHUzMDZlXHU1ODU0IChUb3dlciBvZiBKT0lPSSkiLCJkZXNjcmlwdGlvbiI6IjxwPkpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2OFx1MzA2Zlx1ZmYwYzEgXHU0ZWJhXHUzMDY3XHU5MDRhXHUzMDc2XHU1MTg2XHU3NmU0XHUzMDkyXHU0ZjdmXHUzMDYzXHUzMDVmXHUzMGIyXHUzMGZjXHUzMGUwXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA1M1x1MzA2ZVx1MzBiMlx1MzBmY1x1MzBlMFx1MzA2Zlx1ZmYwY0pcdWZmMGNPXHVmZjBjSSBcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNmVcdTY1ODdcdTViNTdcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNWZcdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdTUxODZcdTc2ZTRcdTMwOTJcdTc1MjhcdTMwNDRcdTMwNjZcdTg4NGNcdTMwNDZcdWZmMGVcdTUxODZcdTc2ZTRcdTMwNmZcdTc2ZjRcdTVmODRcdTMwNGNcdTRlOTJcdTMwNDRcdTMwNmJcdTc1NzBcdTMwNmFcdTMwOGFcdWZmMGNcdTMwYjJcdTMwZmNcdTMwZTBcdTk1OGJcdTU5Y2JcdTY2NDJcdTMwNmJcdTMwNmZcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTUxODZcdTc2ZTRcdTMwNmZcdTc2ZjRcdTVmODRcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNDRcdTMwODJcdTMwNmVcdTMwNGJcdTMwODlcdTk4MDZcdTMwNmJcdTRlMGJcdTMwNGJcdTMwODlcdTRlMGFcdTMwNmJcdTU0MTFcdTMwNGJcdTMwNjNcdTMwNjZcdTdhNGRcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdWZmMGNcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTUxODZcdTc2ZTRcdTMwOTJcdTc1MjhcdTMwNDRcdTMwNjZcdWZmMGNcdTUxZmFcdTY3NjVcdTMwOGJcdTMwNjBcdTMwNTFcdTU5MWFcdTMwNGZcdTMwNmVcdTMwZGZcdTMwY2IgSk9JT0kgXHUzMDZlXHU1ODU0XHUzMDkyXHU0ZjVjXHUzMDhhXHUzMDVmXHUzMDQ0XHVmZjBlXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2OFx1MzA2ZiAzXHU2NzlhXHUzMDZlXHU1MTg2XHU3NmU0XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhhXHVmZjBjXHU1MTg2XHU3NmU0XHUzMDZlXHU3NmY0XHU1Zjg0XHUzMDRjXHU1YzBmXHUzMDU1XHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDRiXHUzMDg5XHU5ODA2XHUzMDZiXHU4YWFkXHUzMDkzXHUzMDY3IEpPSSBcdTMwODJcdTMwNTdcdTMwNGZcdTMwNmYgSU9JIFx1MzA2OFx1OGFhZFx1MzA4MVx1MzA4Ylx1MzA4Mlx1MzA2ZVx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZVx1MzA1Zlx1MzA2MFx1MzA1N1x1ZmYwY1x1NTQwY1x1MzA1OFx1NTE4Nlx1NzZlNFx1MzA5MiAyIFx1NWVhNlx1NGVlNVx1NGUwYVx1NGY3Zlx1MzA0Nlx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2pvaW9pLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjIxMHB4OyB3aWR0aDozNDlweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdTU2ZjM6IEpPSU9JSSBcdTMwNGJcdTMwODlcdTMwNmZcdTMwZGZcdTMwY2IgSk9JT0kgXHUzMDZlXHU1ODU0XHUzMDRjIDIgXHUzMDY0XHU0ZjVjXHUzMDhjXHUzMDhiPFwvcD5cclxuXHJcbjxwPlx1NzUyOFx1NjEwZlx1MzA1NVx1MzA4Y1x1MzA1Zlx1NTE4Nlx1NzZlNFx1MzA2Ylx1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA1Zlx1NjU4N1x1NWI1N1x1MzA0Y1x1MzA1ZFx1MzA4Y1x1MzA1ZVx1MzA4Y1x1NTE4Nlx1NzZlNFx1MzA2ZVx1NzZmNFx1NWY4NFx1MzA0Y1x1NWMwZlx1MzA1NVx1MzA0NFx1MzA4Mlx1MzA2ZVx1MzA0Ylx1MzA4OVx1OTgwNlx1MzA2Ylx1OTU3N1x1MzA1NSBOIFx1MzA2ZVx1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA2OFx1MzA1N1x1MzA2Nlx1NGUwZVx1MzA0OFx1MzA4OVx1MzA4Y1x1MzA4Ylx1ZmYwZVx1MzA1M1x1MzA4Y1x1MzA4OVx1MzA2ZVx1NTE4Nlx1NzZlNFx1MzA5Mlx1NGY3Zlx1MzA2M1x1MzA2Nlx1NGY1Y1x1MzA4Ylx1MzA1M1x1MzA2OFx1MzA2ZVx1MzA2N1x1MzA0ZFx1MzA4Ylx1MzBkZlx1MzBjYiBKT0lPSSBcdTMwNmVcdTU4NTRcdTMwNmVcdTUwMGJcdTY1NzBcdTMwNmVcdTY3MDBcdTU5MjdcdTUwMjRcdTMwOTJcdTZjNDJcdTMwODFcdTMwOGJcdTMwZDdcdTMwZWRcdTMwYjBcdTMwZTlcdTMwZTBcdTMwOTJcdTRmNWNcdTYyMTBcdTMwNWJcdTMwODhcdWZmMGU8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1NmExOVx1NmU5Nlx1NTE2NVx1NTI5Ylx1MzA0Ylx1MzA4OVx1NGVlNVx1NGUwYlx1MzA2ZVx1MzBjN1x1MzBmY1x1MzBiZlx1MzA5Mlx1OGFhZFx1MzA3Zlx1OGZiY1x1MzA4MVx1ZmYwZTxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTc0XHU2NTcwIE4gXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlTiBcdTMwNmZcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmVcdTk1NzdcdTMwNTVcdTMwOTJcdTg4NjhcdTMwNTlcdWZmMGU8XC9saT5cclxuXHQ8bGk+MiBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4xICZsZTsgTiAmbGU7IDEgMDAwIDAwMCBcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmVcdTk1NzdcdTMwNTU8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxZmFcdTUyOWJcdTMwNmJcdWZmMGNcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmVcdTMwNjdcdTMwNGRcdTMwOGJcdTMwZGZcdTMwY2IgSk9JT0kgXHUzMDZlXHU1ODU0XHUzMDZlXHU2NTcwXHUzMDZlXHU2NzAwXHU1OTI3XHU1MDI0XHUzMDkyXHU4ODY4XHUzMDU5XHU2NTc0XHU2NTcwXHUzMDkyIDEgXHU4ODRjXHUzMDY3XHU1MWZhXHU1MjliXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNzdjXHViY2Y4XHVjNWI0In1d

출처

Olympiad > 일본정보올림피아드 > JOI 2013 4번