도장 (Stamp)

IOI 나라에 있는 오래된 도장 제조사 IOI당은 올해로 창업 101주년을 맞는다. 이를 기념해 IOI당은 주문 제작으로 긴 메시지가 새겨진 도장을 만드는 서비스를 시작하기로 했다. 작년에 IOI당은 도장의 특정 부분에 문자를 직접 삽입하거나, 빼내거나, 바꿀 수 있는 도장을 개발해 더 긴 문자열의 도장을 만들 수 있게 했기 때문이다.

이번에 만들 도장은 알파벳 I와 O 두 문자로만 이루어진 IOI어를 대상으로 한다. 또한 기존 기계로 미리 적당한 길이 1 이상의 도장을 만들고, 그 문자열을 적절히 편집해 주문받은 메시지를 만들기로 한다. 다만 오래된 규격 때문에 이 기계로 만들 수 있는 것은 I로 시작하고 I로 끝나며, 어떤 연속한 두 문자도 같지 않은 문자열(예를 들어 I, IOI, IOIO…OIOI)의 도장이다.

현재 IOI당은 일손이 부족해 작업 시간을 최대한 줄이고 싶다. 기계 작업은 시간이 걸리지 않지만, 그 뒤의 3가지 편집 작업, 즉 문자 하나를 삽입하는 작업, 문자 하나를 삭제하는 작업, 문자 하나를 바꾸는 작업은 각각 1회당 1초의 시간이 필요하다. 예를 들어 IOIOIOI라는 문자열의 도장을 기계로 만든 뒤, 3번째 문자를 O로 바꾸고, 5번째 문자와 6번째 문자 사이에 O를 1자 삽입해 IOOOIOOI라는 문자열의 도장을 만들면 2초의 시간이 필요하다.

그래서 주문받은 메시지가 주어졌을 때, 최단 작업 시간과 최단 시간으로 작업할 때 미리 기계로 만들어야 하는 도장 길이의 최솟값을 구하는 프로그램을 작성해 달라.

입력의 1번째 줄에는 주문받은 메시지의 길이를 나타내는 정수 N(1 ≤ N ≤ 1000000)이 쓰여 있다. 2번째 줄에는 주문받은 메시지를 나타내는 N개의 문자 I 또는 O로 이루어진 문자열 S가 쓰여 있다.

출력은 표준 출력으로 한다. 출력의 1번째 줄에는 최단 작업 시간을 쓴다. 2번째 줄에는 최단 시간으로 작업할 때 미리 기계로 만들어야 하는 도장 길이의 최솟값을 쓴다.