끊기지 않는 급수 구간

문제

마라톤 대회의 순환 코스에는 급수대가 일정한 간격으로 놓여 있다. 급수대는 달리는 방향을 따라 1번부터 N번까지 번호가 붙어 있으며, N번 급수대를 지나면 다시 1번 급수대가 나온다. 운영팀은 각 급수대에 물이 충분히 준비되어 있는지 점검하고, 그 결과를 번호 순서대로 하나의 문자열에 기록했다. 문자열에서 1은 사용할 수 있는 급수대를, 0은 사용할 수 없는 급수대를 뜻한다. 운영팀은 참가자에게 안내할 연속 급수 구간을 하나 고르려 한다. 구간의 시작 급수대를 정한 뒤 달리는 방향으로 급수대를 하나씩 포함하며, 포함한 급수대가 모두 사용 가능한 경우에만 올바른 구간으로 인정한다. 구간에 포함하는 급수대의 수는 1개 이상 N개 이하이다. 같은 급수대를 두 번 포함할 수 없으므로, 사용할 수 있는 급수대가 아무리 많아도 한 바퀴를 넘는 구간을 고를 수 없다. 선택할 구간은 포함하는 급수대의 수가 가장 많아야 한다. 그러한 구간이 여러 개라면 시작 급수대의 번호가 가장 작은 구간을 선택한다. 구간이 N번과 1번 사이를 지나더라도 시작 번호는 실제로 처음 포함한 급수대의 번호이다. 예를 들어 마지막 두 급수대와 처음 두 급수대가 이어지는 구간은 마지막에서 두 번째 급수대에서 시작하는 길이 4의 구간이다. 모든 급수대를 사용할 수 있다면 1번에서 시작하여 N개를 포함하는 구간을 선택한다. 사용할 수 있는 급수대가 하나도 없다면 선택할 구간이 없다고 판단한다. 점검 문자열이 주어졌을 때 선택한 구간의 시작 번호와 급수대 수를 구해야 한다. 급수대 사이의 실제 거리와 참가자의 달리기 속도는 계산에 사용하지 않는다.

입력

첫째 줄에 급수대 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어지며, 왼쪽에서 i번째 문자는 i번 급수대의 상태이다.

출력

선택한 구간의 시작 급수대 번호와 포함하는 급수대 수를 공백으로 구분하여 출력한다. 선택할 구간이 없으면 0 0을 출력한다.

10
1101110011

9 4

4
1111

1 4

3
000

0 0

출처: Devin.KR 자체 제작