题目描述

:::align{center}

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_1 s_2 \cdots s_n$ of length $n$ is lexicographically larger than string $t = t_1 t_2 \cdots t_m$ of length $m$, if one of the following holds:

• There exists some $i$ such that, $s_1 = t_1, s_2 = t_2, \cdots, s_{i-1} = t_{i-1}$, and $s_i > t_i$.
• $n > m$ and, $s_1 = t_1, s_2 = t_2, \cdots, s_m = t_m$.

输入格式

In the first line, $N$, the number of stones is given.

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 integers $S, L$. This means that Youngmi removed $L$ stones after $S$-th character. If there is more than one correct answer, print any. ($0 \le S, L \le N$)

8
10101101

1 3

5
11111

0 0

提示

Constraints

• $1 \le N \le 1,000,000$