图:守护郎(Soohorang)。与本题无关,只是因为它很可爱才放进来的。
2018 RUN@KAIST 冬季冰壶比赛女子决赛正在进行中。在 KAIST 结冰的“鸭子塘”上,韩国女子冰壶队正与来自 Jwepan 国的队伍展开激烈角逐!
“鸭子塘”上共有 $N$ 个冰壶。由于竞争异常激烈,每个冰壶都从一个标记处排成一线。最左边的冰壶距离标记最近,而最右边的冰壶距离标记最远。冰壶要么属于韩国队(用 '1' 表示),要么属于 Jwepan 队(用 '0' 表示)。这些冰壶的排列可以用一个长度为 $N$ 的二进制序列来表示。
平昌冬奥会结束后,韩国队进行了高强度的训练。现在,伴随着一些呐喊声(?),负责投壶的队员“荣美(Youngmi)”可以击飞一些连续的冰壶,并将自己的冰壶停留在该位置。形式上,韩国队可以选择二进制字符串中的任意子段(可以为空),并将其替换为单个数字 "1"。
韩国队是冰壶策略的大师,他们知道单回合的最佳策略是使最终的字符串字典序最大!为了在比赛中快速做出决策,他们希望找到一个能实现这一目标的最快算法。请帮助韩国队赢得比赛!
对于长度为 $n$ 的字符串 $s = s_1 s_2 \dots s_n$ 和长度为 $m$ 的字符串 $t = t_1 t_2 \dots t_m$,如果满足以下条件之一,则称 $s$ 的字典序大于 $t$:
- 存在某个 $i$ 使得 $s_1 = t_1, s_2 = t_2, \dots, s_{i-1} = t_{i-1}$,且 $s_i > t_i$。
- $n > m$ 且 $s_1 = t_1, s_2 = t_2, \dots, s_m = t_m$。
输入格式
第一行给定冰壶的数量 $N$。($1 \le N \le 1,000,000$)
第二行给定一个长度为 $N$ 的二进制字符串,由 '0' 或 '1' 组成。该字符串按距离标记由近到远的顺序表示每个冰壶的归属。字符串中不包含引号或空格。
输出格式
输出两个整数 $S, L$。这表示荣美移除了第 $S$ 个字符之后的 $L$ 个冰壶(并在此处放入一个 '1')。如果存在多个正确答案,输出其中任意一个。($0 \le S, L \le N$)
样例
输入样例 1
8 10101101
输出样例 1
1 3
输入样例 2
5 11111
输出样例 2
0 0