시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB158888.889%

문제

IOI 国にある老舗判子メーカーの IOI 堂は今年で創業 101 年となる.これを記念し IOI 堂では オーダーメードで長いメッセージを入れた判子を作るサービスを始めることにした.というの も昨年,IOI 堂は手動で判子の特定の部分に文字を挿入したり,抜き出したり,入れ替えたりす ることができる判子を開発し,より長い文字列の判子を作ることを可能としたのである.

今回作る判子は,アルファベットの I と O の 2 文字のみから構成される IOI 語を対象にす る.また,既存の機械で予め適当な 1 文字以上の長さの判子を作り,その文字列を適宜編集し て注文のメッセージを作ることにする.ただし,古くからの仕様により,この機械で作ること ができるのは,I で始まり I で終わる,どの連続した 2 文字も同一ではない文字列 (例えば I や IOI や IOIO…OIOI) の判子である.

現在,IOI 堂では人手が足りていないので作業時間をできる限り短くしたい.機械作業は時間 がかからないが,その後の3種類の編集作業,すなわち1 つの文字を挿入する作業,1 つの文字を 削除する作業,1 つの文字を入れ替える作業は,各々1 回あたり 1 秒の時間が必要である.例えば IOIOIOI という文字列の判子を機械で作った後に,3 文字目を O に入れ替え,5 文字目と 6 文字 目の間に O を 1 文字挿入し IOOOIOOI という文字列の判子を作ると 2 秒の時間が必要となる.

そこで,注文のメッセージが与えられた時,最短の作業時間と,最短時間で作業した時に予 め機械で作らなければならない判子の長さの最小値を求めるプログラムを書いてほしい.

입력

入力の 1 行目には,1 つの注文されたメッセージの長さを表す整 数 N(1 ≤ N ≤ 1000000) が書かれている.2 行目には注文されたメッセージを表す N 文字の I または O からなる文字列 S が書かれている.

출력

出力は標準出力に行うこと.出力の 1 行目には最短の作業時間を書け.2 行目には最 短時間で作業した時に予め機械で作らなければならない判子の長さの最小値を書け.

예제 입력 1

8
IOOOIOOI

예제 출력 1

2
7

예제 입력 2

5
IOIOI

예제 출력 2

0
5

예제 입력 3

5
IIIII

예제 출력 3

2
5