쉬고 있는 조명 구간

문제

스마트 홈의 거실 천장에는 N개의 조명이 원 모양으로 설치되어 있다. 조명에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. N번 조명의 다음 조명은 1번 조명이다. 관리 화면에는 각 조명의 현재 상태가 번호 순서대로 저장되어 있으며, 상태가 0이면 꺼져 있고 1이면 켜져 있다. 상태를 조사하는 동안 조명이 켜지거나 꺼지는 일은 없다. 집의 관리 장치는 꺼진 조명들이 이어진 구간 하나를 골라 배선 점검을 예약하려 한다. 구간은 시작 조명 하나를 정한 뒤 시계 방향으로 연속한 조명들을 선택하여 만든다. 선택한 조명은 모두 꺼져 있어야 하며, 같은 조명을 두 번 선택할 수 없다. 따라서 구간의 길이는 1 이상 N 이하인 정수이다. 구간이 N번 조명에서 끝나지 않고 1번 조명으로 이어져도 된다. 조명 사이의 실제 거리와 방 안에서의 위치는 선택에 영향을 주지 않는다. 관리 장치는 가능한 구간 중 길이가 가장 긴 구간을 선택한다. 가장 긴 구간이 여러 개라면 시작 조명의 번호가 가장 작은 구간을 선택한다. 여기서 시작 조명은 선택한 구간을 시계 방향으로 따라갈 때 처음 만나는 조명이다. 구간이 1번 조명을 포함하더라도 시작 번호가 반드시 1인 것은 아니다. 예를 들어 끝쪽의 꺼진 조명들에서 출발하여 1번 조명 쪽으로 이어지는 구간은 끝쪽 조명의 번호를 시작 번호로 사용한다. 모든 조명이 꺼져 있다면 어느 조명에서 출발해도 길이가 N인 구간을 만들 수 있으므로 시작 번호가 1인 구간을 선택한다. 반대로 모든 조명이 켜져 있다면 선택할 수 있는 구간이 없다. 조명의 상태 배열을 보고 관리 장치가 선택할 구간의 시작 번호와 길이를 구하는 프로그램을 작성한다.

입력

첫째 줄에 조명의 수 N이 주어진다. N은 1 이상 100,000 이하의 정수이다.
둘째 줄에 1번부터 N번까지의 조명 상태 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 정수 0 또는 1이다.

출력

선택한 구간의 시작 번호와 길이를 공백으로 구분하여 한 줄에 출력한다. 선택할 수 있는 구간이 없다면 0 0을 출력한다.

8
0 0 1 0 0 0 1 0

4 3

4
1 1 1 1

0 0

5
0 0 0 0 0

1 5

출처: Devin.KR 자체 제작