시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 137 49 32 35.165%

문제

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+XHJcblxyXG48cD5cclxuXHRcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVjNzkxXHVjNzQwIFx1YzZkMFx1YmMxOFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNmQwXHViYzE4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmJmOFx1YjJjOCBKT0lPSSBcdWQwZDFcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjNmQwXHViYzE4XHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM2ZDBcdWJjMThcdWM1ZDAgXHVjODAxXHVkNjAwXHVjNzg4XHViMjk0IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVjNzkxXHVjNzQwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEsMDAwLDAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmJmOFx1YjJjOCBKT0lPSSBcdWQwZDFcdWM3NTggXHVjZDVjXHViMzAwIFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNTUzMCIsInByb2JsZW1fbGFuZyI6IjIiLCJ0aXRsZSI6IkpPSU9JIFx1MzA2ZVx1NTg1NCAoVG93ZXIgb2YgSk9JT0kpIiwiZGVzY3JpcHRpb24iOiI8cD5KT0lPSSBcdTMwNmVcdTU4NTRcdTMwNjhcdTMwNmZcdWZmMGMxIFx1NGViYVx1MzA2N1x1OTA0YVx1MzA3Nlx1NTE4Nlx1NzZlNFx1MzA5Mlx1NGY3Zlx1MzA2M1x1MzA1Zlx1MzBiMlx1MzBmY1x1MzBlMFx1MzA2N1x1MzA0Mlx1MzA4Ylx1ZmYwZTxcL3A+XHJcblxyXG48cD5cdTMwNTNcdTMwNmVcdTMwYjJcdTMwZmNcdTMwZTBcdTMwNmZcdWZmMGNKXHVmZjBjT1x1ZmYwY0kgXHUzMDZlXHUzMDQ0XHUzMDVhXHUzMDhjXHUzMDRiXHUzMDZlXHU2NTg3XHU1YjU3XHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDVmXHUzMDQ0XHUzMDRmXHUzMDY0XHUzMDRiXHUzMDZlXHU1MTg2XHU3NmU0XHUzMDkyXHU3NTI4XHUzMDQ0XHUzMDY2XHU4ODRjXHUzMDQ2XHVmZjBlXHU1MTg2XHU3NmU0XHUzMDZmXHU3NmY0XHU1Zjg0XHUzMDRjXHU0ZTkyXHUzMDQ0XHUzMDZiXHU3NTcwXHUzMDZhXHUzMDhhXHVmZjBjXHUzMGIyXHUzMGZjXHUzMGUwXHU5NThiXHU1OWNiXHU2NjQyXHUzMDZiXHUzMDZmXHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZlXHU1MTg2XHU3NmU0XHUzMDZmXHU3NmY0XHU1Zjg0XHUzMDZlXHU1OTI3XHUzMDRkXHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDRiXHUzMDg5XHU5ODA2XHUzMDZiXHU0ZTBiXHUzMDRiXHUzMDg5XHU0ZTBhXHUzMDZiXHU1NDExXHUzMDRiXHUzMDYzXHUzMDY2XHU3YTRkXHUzMDdlXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlXHUzMDQyXHUzMDZhXHUzMDVmXHUzMDZmXHVmZjBjXHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZlXHU1MTg2XHU3NmU0XHUzMDkyXHU3NTI4XHUzMDQ0XHUzMDY2XHVmZjBjXHU1MWZhXHU2NzY1XHUzMDhiXHUzMDYwXHUzMDUxXHU1OTFhXHUzMDRmXHUzMDZlXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA5Mlx1NGY1Y1x1MzA4YVx1MzA1Zlx1MzA0NFx1ZmYwZVx1MzBkZlx1MzBjYiBKT0lPSSBcdTMwNmVcdTU4NTRcdTMwNjhcdTMwNmYgM1x1Njc5YVx1MzA2ZVx1NTE4Nlx1NzZlNFx1MzA0Ylx1MzA4OVx1MzA2YVx1MzA4YVx1ZmYwY1x1NTE4Nlx1NzZlNFx1MzA2ZVx1NzZmNFx1NWY4NFx1MzA0Y1x1NWMwZlx1MzA1NVx1MzA0NFx1MzA4Mlx1MzA2ZVx1MzA0Ylx1MzA4OVx1OTgwNlx1MzA2Ylx1OGFhZFx1MzA5M1x1MzA2NyBKT0kgXHUzMDgyXHUzMDU3XHUzMDRmXHUzMDZmIElPSSBcdTMwNjhcdThhYWRcdTMwODFcdTMwOGJcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTU0MGNcdTMwNThcdTUxODZcdTc2ZTRcdTMwOTIgMiBcdTVlYTZcdTRlZTVcdTRlMGFcdTRmN2ZcdTMwNDZcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9qb2lvaS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMTBweDsgd2lkdGg6MzQ5cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHU1NmYzOiBKT0lPSUkgXHUzMDRiXHUzMDg5XHUzMDZmXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA0YyAyIFx1MzA2NFx1NGY1Y1x1MzA4Y1x1MzA4YjxcL3A+XHJcblxyXG48cD5cdTc1MjhcdTYxMGZcdTMwNTVcdTMwOGNcdTMwNWZcdTUxODZcdTc2ZTRcdTMwNmJcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNWZcdTY1ODdcdTViNTdcdTMwNGNcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGNcdTUxODZcdTc2ZTRcdTMwNmVcdTc2ZjRcdTVmODRcdTMwNGNcdTVjMGZcdTMwNTVcdTMwNDRcdTMwODJcdTMwNmVcdTMwNGJcdTMwODlcdTk4MDZcdTMwNmJcdTk1NzdcdTMwNTUgTiBcdTMwNmVcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNjhcdTMwNTdcdTMwNjZcdTRlMGVcdTMwNDhcdTMwODlcdTMwOGNcdTMwOGJcdWZmMGVcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTUxODZcdTc2ZTRcdTMwOTJcdTRmN2ZcdTMwNjNcdTMwNjZcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmVcdTMwNjdcdTMwNGRcdTMwOGJcdTMwZGZcdTMwY2IgSk9JT0kgXHUzMDZlXHU1ODU0XHUzMDZlXHU1MDBiXHU2NTcwXHUzMDZlXHU2NzAwXHU1OTI3XHU1MDI0XHUzMDkyXHU2YzQyXHUzMDgxXHUzMDhiXHUzMGQ3XHUzMGVkXHUzMGIwXHUzMGU5XHUzMGUwXHUzMDkyXHU0ZjVjXHU2MjEwXHUzMDViXHUzMDg4XHVmZjBlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdTZhMTlcdTZlOTZcdTUxNjVcdTUyOWJcdTMwNGJcdTMwODlcdTRlZTVcdTRlMGJcdTMwNmVcdTMwYzdcdTMwZmNcdTMwYmZcdTMwOTJcdThhYWRcdTMwN2ZcdThmYmNcdTMwODFcdWZmMGU8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU3NFx1NjU3MCBOIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZU4gXHUzMDZmXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZlXHU5NTc3XHUzMDU1XHUzMDkyXHU4ODY4XHUzMDU5XHVmZjBlPFwvbGk+XHJcblx0PGxpPjIgXHU4ODRjXHU3NmVlXHUzMDZiXHUzMDZmXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDRjXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDY2XHUzMDQ0XHUzMDhiXHVmZjBlPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+MSAmbGU7IE4gJmxlOyAxIDAwMCAwMDAgXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDZlXHU5NTc3XHUzMDU1PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MWZhXHU1MjliXHUzMDZiXHVmZjBjXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZlXHUzMDY3XHUzMDRkXHUzMDhiXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2ZVx1NjU3MFx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1Yzc3Y1x1YmNmOFx1YzViNCJ9XQ==

출처

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