405145: GYM101806 W Winter Olympic Games

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 = s_1s2... s_n of length n is lexicographically larger than string t = t_1t2... t_m of length m, if one of the following holds:

• There exists some i such that, s₁ = t₁, s₂ = t₂, ..., s_i - 1 = t_i - 1, and s_i > t_i.
• n > m and, s₁ = t₁, s₂ = t₂, ..., s_m = t_m.

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.

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)

8
10101101

1 3

5
11111

0 0