W. Winter Olympic Games
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Figure: "Soohorang" - Not related to this problem, but included just because it's cute.

2018 RUN@KAIST Winter Curling Competition women's finals game is now ongoing. On the frozen "duck pond" of KAIST, Korean women curling team is having a fierce competition with team from country Jwepan!

There are N curling stones on the "duck pond". As the competition is really fierce, every stone is placed in a line from a mark. The leftmost stone is closest from the mark, while the rightmost stone is farthest from the mark. Stones are either from Korean team ('1'), or from Jwepan team ('0'). Those arrangement of stones can be represented with length N binary sequence.

After the end of Pyeongchang Olympics, Korean team had gone through intensive training. Now with some shoutings(?), team member "Youngmi", who carries the curling stone, can bounce away some consecutive stones and place her stone in that position. Formally, Korean team can pick any subsegment in a binary string (which can be empty), and replace it into a single digit "1".

Korean team is a master in a curling strategy, and they knew the best strategy for one turn is to make the string lexicographically maximal! For the fast decision making in this game, they want to find a fastest algorithm which can find this. Help the Korean team to win the competition!

String s = s1s2... sn of length n is lexicographically larger than string t = t1t2... tm of length m, if one of the following holds:

  • There exists some i such that, s1 = t1, s2 = t2, ..., si - 1 = ti - 1, and si > ti.
  • n > m and, s1 = t1, s2 = t2, ..., sm = tm.
Input

In the first line, N, the number of stones is given. (1 ≤ N ≤ 1, 000, 000)

In the second line, A single binary string of length N, which consists of '0' or '1' is given. This string indicates the owner of each curling stone, in the order of distance from the mark. There are no quotes or blanks given in the string.

Output

Print two integer S,  L. This means that Youngmi removed L stones after Sth character. If there is more than one correct answer, print any. (0 ≤ S,  L ≤ N)

Examples
Input
8
10101101
Output
1 3
Input
5
11111
Output
0 0