원형 복도의 빈 객실

문제

한 호텔의 한 층에는 객실 N개가 원형 복도를 따라 배치되어 있다. 객실 번호는 1번부터 N번까지이며, 번호가 증가하는 방향으로 걸으면 N번 객실 다음에는 다시 1번 객실이 나온다. 호텔 관리자는 단체 손님에게 서로 이어진 빈 객실을 배정하려고 한다. 현재 객실 상태는 길이가 N인 문자열 S로 주어진다. 왼쪽에서 i번째 문자가 0이면 i번 객실이 비어 있고, 1이면 이미 사용 중이다. 배정 후보는 시작 객실 하나와 양의 정수인 객실 수를 정하여 만든다. 시작 객실부터 번호가 증가하는 방향으로 정한 수만큼 객실을 확인했을 때, 확인한 모든 객실이 비어 있어야 유효한 후보가 된다. 복도가 원형이므로 후보에 N번 객실과 1번 객실이 함께 들어갈 수 있다. 다만 같은 객실을 두 번 포함할 수 없으므로 후보의 객실 수는 N 이하여야 한다. 후보를 확인하는 도중 사용 중인 객실을 건너뛸 수는 없다. 관리자는 유효한 후보 중 객실 수가 가장 많은 것을 선택한다. 가장 많은 객실 수를 가진 후보가 여러 개라면 시작 객실 번호가 가장 작은 것을 선택한다. 시작 번호가 작다는 이유로 더 적은 객실을 선택하지는 않는다. 모든 객실이 비어 있다면 객실 N개를 모두 선택하고 시작 객실은 1번으로 정한다. 빈 객실이 하나도 없다면 유효한 후보가 없으므로 시작 객실 번호와 객실 수를 모두 0으로 기록한다. 객실의 상태를 바꾸거나 새로운 손님을 실제로 배정하는 작업은 하지 않는다. 주어진 현재 상태만 이용하여 관리자가 기록할 시작 객실 번호와 객실 수를 구하는 프로그램을 작성한다.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 0과 1로만 이루어진다. 각 문자는 해당 번호 객실의 현재 상태를 나타낸다.

출력

선택한 후보의 시작 객실 번호와 객실 수를 공백으로 구분하여 한 줄에 출력한다. 유효한 후보가 없으면 0 0을 출력한다.

8
00100010

4 3

5
00000

1 5

4
1111

0 0

출처: Devin.KR 자체 제작