시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB38615512740.836%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

6
JOIIOI

예제 출력 1

2

예제 입력 2

5
JOIOI

예제 출력 2

1

예제 입력 3

6
JOIOII

예제 출력 3

2

예제 입력 4

15
JJOIIOOJOJIOIIO

예제 출력 4

4
W3sicHJvYmxlbV9pZCI6IjU1MzAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJKT0lPSSBcdWQwZDEiLCJkZXNjcmlwdGlvbiI6IjxwPkpPSU9JIFx1ZDBkMVx1Yzc0MCBcdWM2ZDBcdWJjMThcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1ZDYzY1x1Yzc5MCBcdWM3YWNcdWJiZjhcdWM3ODhcdWFjOGMgXHViMTgwIFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzQgXHVhYzhjXHVjNzg0XHVjNzQwIDxjb2RlPko8XC9jb2RlPiwgPGNvZGU+TzxcL2NvZGU+LCA8Y29kZT5JPFwvY29kZT5cdWM5MTEgXHVkNTU4XHViMDk4XHVjNzU4IFx1YmIzOFx1Yzc5MFx1YWMwMCBcdWM0ZjBcdWM1ZWNcdWM5YzQgXHVjNmQwXHViYzE4XHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNmQwXHViYzE4XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHViMmU0XHViOTc0XHViMmU0LiBcdWFjMDBcdWM3YTUgXHVjYzk4XHVjNzRjXHVjNWQwIFx1YzZkMFx1YmMxOFx1Yzc0MCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVkMDcwIFx1YWM4M1x1Yzc3NCBcdWFjMDBcdWM3YTUgXHVjNTQ0XHViNzk4XHVjNWQwIFx1Yzc4OFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwXHViMjk0IFx1Yzc5MVx1YzU0NFx1YzljMFx1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjMzEzXHVjNWVjIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1Yzc3NCBcdWM2ZDBcdWJjMThcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWI5Y2VcdWM3NDAgXHViYmY4XHViMmM4IEpPSU9JIFx1ZDBkMVx1Yzc0NCBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiZjhcdWIyYzggSk9JT0kgXHVkMGQxXHVjNzQwIDNcdWFjMWNcdWM3NTggXHVjNmQwXHViYzE4XHVjNzNjXHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxOFx1YmE3MCwgXHViYzE4XHVjOWMwXHViOTg0XHVjNzc0IFx1Yzc5MVx1Yzc0MCBcdWFjODNcdWJkODBcdWQxMzAgXHVjNzdkXHVjNWM4XHVjNzQ0IFx1YjU0YyA8Y29kZT5KT0k8XC9jb2RlPlx1YjA5OCA8Y29kZT5JT0k8XC9jb2RlPlx1Yzc3NFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1ZDU1YyBcdWJiZjhcdWIyYzggSk9JT0kgXHVkMGQxXHVjNWQwIFx1YzE4ZFx1ZDU1YyBcdWM2ZDBcdWJjMThcdWM3NDAgXHViMmU0XHViOTc4IFx1ZDBkMVx1YzVkMCBcdWMxOGRcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81OGNiYTAyMi05MDUzLTRlNjktOTY0Zi00MjVmOTQ0ZDM1OWJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMzMnB4OyBoZWlnaHQ6IDE5OXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgXHVjNzkxXHVjNzQwIFx1YzZkMFx1YmMxOFx1YmQ4MFx1ZDEzMCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNmQwXHViYzE4XHVjNWQwIFx1YzgwMVx1ZDYwMFx1YzgzOCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYmY4XHViMmM4IEpPSU9JIFx1ZDBkMVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM2ZDBcdWJjMThcdWM3NTggXHVhYzFjXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWI0NThcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzZkMFx1YmMxOFx1YzVkMCBcdWM4MDFcdWQ2MDBcdWM3ODhcdWIyOTQgXHViYjM4XHVjNzkwXHVhYzAwIFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NCBcdWM3OTFcdWM3NDAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDEgJmxlOyBOICZsZTsgMSwwMDAsMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHViYmY4XHViMmM4IEpPSU9JIFx1ZDBkMVx1Yzc1OCBcdWNkNWNcdWIzMDAgXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1NTMwIiwicHJvYmxlbV9sYW5nIjoiMiIsInRpdGxlIjoiSk9JT0kgXHUzMDZlXHU1ODU0IChUb3dlciBvZiBKT0lPSSkiLCJkZXNjcmlwdGlvbiI6IjxwPkpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2OFx1MzA2Zlx1ZmYwYzEgXHU0ZWJhXHUzMDY3XHU5MDRhXHUzMDc2XHU1MTg2XHU3NmU0XHUzMDkyXHU0ZjdmXHUzMDYzXHUzMDVmXHUzMGIyXHUzMGZjXHUzMGUwXHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuXHJcbjxwPlx1MzA1M1x1MzA2ZVx1MzBiMlx1MzBmY1x1MzBlMFx1MzA2Zlx1ZmYwYzxjb2RlPko8XC9jb2RlPlx1ZmYwYzxjb2RlPk88XC9jb2RlPlx1ZmYwYzxjb2RlPkk8XC9jb2RlPiBcdTMwNmVcdTMwNDRcdTMwNWFcdTMwOGNcdTMwNGJcdTMwNmVcdTY1ODdcdTViNTdcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNWZcdTMwNDRcdTMwNGZcdTMwNjRcdTMwNGJcdTMwNmVcdTUxODZcdTc2ZTRcdTMwOTJcdTc1MjhcdTMwNDRcdTMwNjZcdTg4NGNcdTMwNDZcdWZmMGVcdTUxODZcdTc2ZTRcdTMwNmZcdTc2ZjRcdTVmODRcdTMwNGNcdTRlOTJcdTMwNDRcdTMwNmJcdTc1NzBcdTMwNmFcdTMwOGFcdWZmMGNcdTMwYjJcdTMwZmNcdTMwZTBcdTk1OGJcdTU5Y2JcdTY2NDJcdTMwNmJcdTMwNmZcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTUxODZcdTc2ZTRcdTMwNmZcdTc2ZjRcdTVmODRcdTMwNmVcdTU5MjdcdTMwNGRcdTMwNDRcdTMwODJcdTMwNmVcdTMwNGJcdTMwODlcdTk4MDZcdTMwNmJcdTRlMGJcdTMwNGJcdTMwODlcdTRlMGFcdTMwNmJcdTU0MTFcdTMwNGJcdTMwNjNcdTMwNjZcdTdhNGRcdTMwN2VcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVcdTMwNDJcdTMwNmFcdTMwNWZcdTMwNmZcdWZmMGNcdTMwNTNcdTMwOGNcdTMwODlcdTMwNmVcdTUxODZcdTc2ZTRcdTMwOTJcdTc1MjhcdTMwNDRcdTMwNjZcdWZmMGNcdTUxZmFcdTY3NjVcdTMwOGJcdTMwNjBcdTMwNTFcdTU5MWFcdTMwNGZcdTMwNmVcdTMwZGZcdTMwY2IgSk9JT0kgXHUzMDZlXHU1ODU0XHUzMDkyXHU0ZjVjXHUzMDhhXHUzMDVmXHUzMDQ0XHVmZjBlXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2OFx1MzA2ZiAzXHU2NzlhXHUzMDZlXHU1MTg2XHU3NmU0XHUzMDRiXHUzMDg5XHUzMDZhXHUzMDhhXHVmZjBjXHU1MTg2XHU3NmU0XHUzMDZlXHU3NmY0XHU1Zjg0XHUzMDRjXHU1YzBmXHUzMDU1XHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDRiXHUzMDg5XHU5ODA2XHUzMDZiXHU4YWFkXHUzMDkzXHUzMDY3IDxjb2RlPkpPSTxcL2NvZGU+IFx1MzA4Mlx1MzA1N1x1MzA0Zlx1MzA2ZiA8Y29kZT5JT0k8XC9jb2RlPiBcdTMwNjhcdThhYWRcdTMwODFcdTMwOGJcdTMwODJcdTMwNmVcdTMwNjdcdTMwNDJcdTMwOGJcdWZmMGVcdTMwNWZcdTMwNjBcdTMwNTdcdWZmMGNcdTU0MGNcdTMwNThcdTUxODZcdTc2ZTRcdTMwOTIgMiBcdTVlYTZcdTRlZTVcdTRlMGFcdTRmN2ZcdTMwNDZcdTMwNTNcdTMwNjhcdTMwNmZcdTMwNjdcdTMwNGRcdTMwNmFcdTMwNDRcdWZmMGU8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81OGNiYTAyMi05MDUzLTRlNjktOTY0Zi00MjVmOTQ0ZDM1OWJcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMzMnB4OyBoZWlnaHQ6IDE5OXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5cdTU2ZjM6IDxjb2RlPkpPSU9JSTxcL2NvZGU+IFx1MzA0Ylx1MzA4OVx1MzA2Zlx1MzBkZlx1MzBjYiBKT0lPSSBcdTMwNmVcdTU4NTRcdTMwNGMgMiBcdTMwNjRcdTRmNWNcdTMwOGNcdTMwOGI8XC9wPlxyXG5cclxuPHA+XHU3NTI4XHU2MTBmXHUzMDU1XHUzMDhjXHUzMDVmXHU1MTg2XHU3NmU0XHUzMDZiXHU2NmY4XHUzMDRiXHUzMDhjXHUzMDVmXHU2NTg3XHU1YjU3XHUzMDRjXHUzMDVkXHUzMDhjXHUzMDVlXHUzMDhjXHU1MTg2XHU3NmU0XHUzMDZlXHU3NmY0XHU1Zjg0XHUzMDRjXHU1YzBmXHUzMDU1XHUzMDQ0XHUzMDgyXHUzMDZlXHUzMDRiXHUzMDg5XHU5ODA2XHUzMDZiXHU5NTc3XHUzMDU1IE4gXHUzMDZlXHU2NTg3XHU1YjU3XHU1MjE3IFMgXHUzMDY4XHUzMDU3XHUzMDY2XHU0ZTBlXHUzMDQ4XHUzMDg5XHUzMDhjXHUzMDhiXHVmZjBlXHUzMDUzXHUzMDhjXHUzMDg5XHUzMDZlXHU1MTg2XHU3NmU0XHUzMDkyXHU0ZjdmXHUzMDYzXHUzMDY2XHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZlXHUzMDY3XHUzMDRkXHUzMDhiXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2ZVx1NTAwYlx1NjU3MFx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA5Mlx1NmM0Mlx1MzA4MVx1MzA4Ylx1MzBkN1x1MzBlZFx1MzBiMFx1MzBlOVx1MzBlMFx1MzA5Mlx1NGY1Y1x1NjIxMFx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MTY1XHU1MjliXHUzMDRiXHUzMDg5XHU0ZWU1XHU0ZTBiXHUzMDZlXHUzMGM3XHUzMGZjXHUzMGJmXHUzMDkyXHU4YWFkXHUzMDdmXHU4ZmJjXHUzMDgxXHVmZjBlPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSBcdTg4NGNcdTc2ZWVcdTMwNmJcdTMwNmZcdTY1NzRcdTY1NzAgTiBcdTMwNGNcdTY2ZjhcdTMwNGJcdTMwOGNcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGVOIFx1MzA2Zlx1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA2ZVx1OTU3N1x1MzA1NVx1MzA5Mlx1ODg2OFx1MzA1OVx1ZmYwZTxcL2xpPlxyXG5cdDxsaT4yIFx1ODg0Y1x1NzZlZVx1MzA2Ylx1MzA2Zlx1NjU4N1x1NWI1N1x1NTIxNyBTIFx1MzA0Y1x1NjZmOFx1MzA0Ylx1MzA4Y1x1MzA2Nlx1MzA0NFx1MzA4Ylx1ZmYwZTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHU2YTE5XHU2ZTk2XHU1MWZhXHU1MjliXHUzMDZiXHVmZjBjXHU0ZjVjXHUzMDhiXHUzMDUzXHUzMDY4XHUzMDZlXHUzMDY3XHUzMDRkXHUzMDhiXHUzMGRmXHUzMGNiIEpPSU9JIFx1MzA2ZVx1NTg1NFx1MzA2ZVx1NjU3MFx1MzA2ZVx1NjcwMFx1NTkyN1x1NTAyNFx1MzA5Mlx1ODg2OFx1MzA1OVx1NjU3NFx1NjU3MFx1MzA5MiAxIFx1ODg0Y1x1MzA2N1x1NTFmYVx1NTI5Ylx1MzA1Ylx1MzA4OFx1ZmYwZTxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkphcGFuZXNlIiwibGltaXQiOiI8cD4xICZsZTsgTiAmbGU7IDEgMDAwIDAwMCBcdTY1ODdcdTViNTdcdTUyMTcgUyBcdTMwNmVcdTk1NzdcdTMwNTU8XC9wPlxyXG4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+PGNvZGU+Sk9JSU9JPFwvY29kZT4gXHUzMDZmIDxjb2RlPkpPSTxcL2NvZGU+IFx1MzA0YVx1MzA4OFx1MzA3MyA8Y29kZT5JT0k8XC9jb2RlPiBcdTMwOTJcdTMwNWRcdTMwOGNcdTMwNWVcdTMwOGMgMSBcdTMwNjRcdTMwNWFcdTMwNjRcdTkwZThcdTUyMDZcdTUyMTdcdTMwNjhcdTMwNTdcdTMwNjZcdTU0MmJcdTMwOTNcdTMwNjdcdTMwNGFcdTMwOGFcdWZmMGNcdTRmNWNcdTMwOGJcdTMwNTNcdTMwNjhcdTMwNmVcdTMwNjdcdTMwNGRcdTMwOGJcdTMwZGZcdTMwY2IgSk9JT0kgXHUzMDZlXHU1ODU0XHUzMDZmIDIgXHUzMDY0XHUzMDY3XHUzMDQyXHUzMDhiXHVmZjBlPFwvcD5cclxuIiwic2FtcGxlX2V4cGxhaW5fMiI6IjxwPlx1OTBlOFx1NTIwNlx1NTIxN1x1MzA2OFx1MzA1N1x1MzA2NiA8Y29kZT5KT0k8XC9jb2RlPiBcdTMwNGFcdTMwODhcdTMwNzMgPGNvZGU+SU9JPFwvY29kZT4gXHUzMDkyXHU1NDJiXHUzMDkzXHUzMDY3XHUzMDQ0XHUzMDhiXHUzMDRjXHVmZjBjXHU2NTg3XHU1YjU3XHUzMDkyIDIgXHU1ZWE2XHU0ZWU1XHU0ZTBhXHU0ZjdmXHUzMDQ2XHUzMDUzXHUzMDY4XHUzMDZmXHUzMDY3XHUzMDRkXHUzMDZhXHUzMDQ0XHUzMDVmXHUzMDgxXHU1NDBjXHU2NjQyXHUzMDZiXHU1M2Q2XHUzMDhhXHU1MWZhXHUzMDU5IFx1MzA1M1x1MzA2OFx1MzA2Zlx1MzA2N1x1MzA0ZFx1MzA2YVx1MzA0NFx1ZmYwZTxcL3A+XHJcbiIsInNhbXBsZV9leHBsYWluXzMiOiI8cD5cdTMwNTNcdTMwNmVcdTUxNjVcdTUxZmFcdTUyOWJcdTRmOGJcdTMwNmZcdTU1NGZcdTk4NGNcdTY1ODdcdTRlMmRcdTMwNmVcdTRmOGJcdTMwNmJcdTViZmVcdTVmZGNcdTMwNTdcdTMwNjZcdTMwNDRcdTMwOGJcdWZmMGU8XC9wPlxyXG4ifV0=

출처

Olympiad > Japanese Olympiad in Informatics > JOI 2013 4번