빈 대여소가 이어진 구간

문제

공유 자전거 관리 구역에는 한 산책로를 따라 N개의 대여소가 놓여 있다. 대여소에는 산책로의 한쪽 끝부터 차례대로 1번부터 N번까지 번호가 붙어 있다. 관리자는 같은 시각에 모든 대여소를 확인하고, 각 대여소에서 바로 빌릴 수 있는 자전거 수를 번호 순서대로 배열에 기록했다. 기록한 수가 0인 대여소를 빈 대여소라고 한다. 자전거가 한 대라도 있으면 빈 대여소가 아니다. 관리자는 자전거를 보충할 곳을 정하기 전에 빈 대여소가 가장 길게 이어진 구간을 찾으려고 한다. 하나의 구간은 시작 번호부터 끝 번호까지의 모든 대여소를 포함한다. 구간에 속한 대여소는 번호가 연속해야 하며, 그 안의 모든 대여소가 비어 있어야 한다. 빈 대여소 사이에 자전거가 있는 대여소가 하나라도 끼어 있으면 두 부분을 하나의 구간으로 합칠 수 없다. 구간의 길이는 그 안에 포함된 대여소의 개수다. 조건을 만족하는 구간 중 길이가 가장 긴 구간을 선택한다. 가장 긴 구간이 여러 개라면 시작 번호가 가장 작은 구간을 선택한다. 대여소는 일렬로 놓여 있으므로 N번 대여소 다음에 1번 대여소가 이어진다고 보지 않는다. 첫 번째 대여소나 마지막 대여소가 선택한 구간에 포함되어도 된다. 빈 대여소가 하나뿐인 구간도 길이가 1인 올바른 구간이다. 선택한 구간의 시작 번호와 길이를 구하는 프로그램을 작성한다. 빈 대여소가 전혀 없다면 구간을 선택할 수 없으므로 시작 번호와 길이 대신 0과 0을 출력한다. 이 작업에서는 기록된 배열만 확인하며, 자전거를 옮기거나 기록된 수를 바꾸지 않는다.

입력

첫째 줄에 대여소 수 N이 주어진다. N은 1 이상 1,000 이하의 정수다.
둘째 줄에 각 대여소의 자전거 수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. A_i는 i번 대여소의 자전거 수이며, 각각 0 이상 100 이하의 정수다.

출력

선택한 구간의 시작 번호와 길이를 순서대로 공백 하나로 구분하여 한 줄에 출력한다. 길이가 같은 구간이 여러 개라면 시작 번호가 가장 작은 구간의 정보를 출력한다. 빈 대여소가 없으면 0 0을 출력한다.

9
2 0 0 3 0 0 4 0 1

2 2

4
1 5 2 3

0 0

5
0 0 0 0 0

1 5

출처: Devin.KR 자체 제작