Stamp

IOI-do, a long-established stamp maker in the country of IOI, celebrates its 101st anniversary this year. To mark the occasion, IOI-do will start a service that makes custom stamps carrying long messages. Last year IOI-do developed a stamp whose specific parts can be edited by hand, inserting, removing, or replacing characters, which made it possible to produce stamps with longer strings.

The stamps made this time target the IOI language, which consists of only the two letters I and O. An existing machine first makes a stamp of some suitable length of at least 1, and that string is then edited as needed to produce the ordered message. Because of an old specification, however, this machine can only make stamps that start with I, end with I, and have no two consecutive characters equal (for example, I, IOI, IOIO...OIOI).

IOI-do is short-staffed right now, so it wants to keep the working time as short as possible. Machine work takes no time, but the three kinds of editing that follow, inserting one character, deleting one character, and replacing one character, each take 1 second per operation. For example, after the machine makes a stamp with the string IOIOIOI, replacing the 3rd character with O and inserting one O between the 5th and 6th characters produces the stamp with the string IOOOIOOI, which takes 2 seconds.

Given an ordered message, write a program that finds the shortest working time and, among workings that achieve that shortest time, the minimum length of the stamp the machine must make in advance.

The first line of the input contains an integer N (1 ≤ N ≤ 1000000), the length of one ordered message. The second line contains a string S of N characters, each I or O, representing the ordered message.

Write the output to standard output. The first line of the output holds the shortest working time. The second line holds the minimum length of the stamp the machine must make in advance when working in the shortest time.