함께 앉을 수 있는 자리

문제

지하철의 한 객실에는 한쪽 벽을 따라 좌석 N개가 한 줄로 놓여 있다. 좌석에는 왼쪽부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 안내 화면은 현재 각 좌석이 비어 있는지를 길이 N인 문자열로 보여 준다. 문자열의 i번째 문자가 '1'이면 i번 좌석이 비어 있고, '0'이면 이미 다른 승객이 앉아 있다는 뜻이다. 함께 탄 승객들은 서로 떨어지지 않고 나란히 앉을 수 있는 자리를 찾고 있다. 이를 돕기 위해 안내 화면에는 연속해서 비어 있는 좌석 구간 중 가장 긴 구간 하나를 표시하려고 한다. 여기서 구간은 번호가 하나씩 증가하는 좌석들로 이루어져야 하며, 구간 안의 모든 좌석이 비어 있어야 한다. 구간의 길이는 그 안에 포함된 좌석의 수이다. 이미 승객이 앉아 있는 좌석을 건너뛰어 두 구간을 연결할 수는 없다. 또한 좌석들은 한 줄로 놓여 있으므로 마지막 N번 좌석과 첫 번째 1번 좌석은 이어져 있지 않다. 문자열의 양 끝이 모두 '1'이더라도 그 두 부분을 하나의 구간으로 합치지 않는다. 안내 화면을 계산하는 동안 승객의 이동이나 좌석 상태의 변화는 일어나지 않는다. 가장 긴 구간이 여러 개라면 시작 좌석 번호가 가장 작은 구간을 표시한다. 안내 화면에 필요한 정보는 선택한 구간의 시작 좌석 번호와 길이이다. 비어 있는 좌석이 하나도 없다면 선택할 수 있는 구간이 없으므로 시작 번호와 길이를 모두 0으로 기록한다. 좌석 하나만 비어 있는 구간도 길이가 1인 올바른 구간이다. 예를 들어 상태가 0110110이라면 2번부터 3번까지와 5번부터 6번까지가 각각 길이 2인 빈 좌석 구간이다. 두 구간의 길이가 같으므로 시작 번호가 더 작은 2번부터의 구간을 선택한다. 모든 좌석이 비어 있다면 1번부터 N번까지를 선택한다. N은 1 이상 1,000 이하의 정수이다. 좌석 상태가 주어졌을 때 안내 화면에 표시할 시작 좌석 번호와 구간의 길이를 구하는 프로그램을 작성한다.

입력

첫째 줄에 좌석 수 N이 주어진다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다.
N은 1 이상 1,000 이하의 정수이며, S는 문자 '0'과 '1'로만 이루어진다.

출력

첫째 줄에 선택한 구간의 시작 좌석 번호와 길이를 공백으로 구분하여 출력한다. 가장 긴 구간이 여러 개면 시작 좌석 번호가 가장 작은 구간을 선택한다. 빈 좌석이 없으면 0 0을 출력한다.

11
10111001110

3 3

5
00000

0 0

6
110111

4 3

출처: Devin.KR 자체 제작