한 줄의 점검 자리

문제

사내 IT 지원실에는 점검용 컴퓨터를 올려놓는 자리가 한 줄로 배치되어 있다. 자리에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 지원팀은 여러 대의 컴퓨터를 동시에 점검하기 위해, 현재 비어 있는 자리 중 서로 연속한 자리를 최대한 많이 확보하려고 한다. 각 자리의 상태는 정수 하나로 주어진다. 상태가 0이면 아무 장비도 없는 빈 자리다. 상태가 1이면 사용 중인 장비가 있고, 상태가 2이면 수리 중인 장비가 있다. 상태가 1인 자리와 2인 자리는 모두 새 컴퓨터를 놓을 수 없는 자리이며, 이미 놓인 장비를 옮기거나 치울 수는 없다. 지원팀이 선택하는 구간은 시작 자리부터 끝 자리까지 빠짐없이 이어지는 하나의 구간이어야 한다. 선택한 구간에 포함된 모든 자리의 상태가 0이어야 하며, 구간의 길이는 그 안에 들어 있는 자리의 개수다. 양 끝 자리가 모두 비어 있더라도 그 사이에 사용할 수 없는 자리가 하나라도 있으면 하나의 구간으로 선택할 수 없다. 또한 자리들은 직선으로 놓여 있으므로 N번 자리와 1번 자리는 서로 이어져 있지 않다. 지원팀은 선택할 수 있는 구간 중 길이가 가장 긴 구간을 사용한다. 가장 긴 구간이 여러 개라면 시작 자리 번호가 가장 작은 구간을 사용한다. 선택한 구간 안에서는 비어 있는 자리를 일부 남길 필요가 없으며, 전체 길이가 최대가 되도록 결정한다. 자리 상태 배열이 주어졌을 때 지원팀이 사용할 구간의 시작 자리 번호와 길이를 구한다. 빈 자리가 하나도 없다면 구간을 선택할 수 없으므로 시작 자리 번호와 길이를 모두 0으로 정한다. 빈 자리가 하나라도 있다면 시작 자리 번호는 반드시 1 이상이고 길이도 1 이상이어야 한다.

입력

첫째 줄에 자리 수 N이 주어진다. N은 1 이상 100,000 이하인 정수다.
둘째 줄에 1번 자리부터 N번 자리까지의 상태가 공백으로 구분되어 주어진다. 각 상태는 정수 0, 1, 2 중 하나다.

출력

선택한 구간의 시작 자리 번호와 길이를 공백으로 구분하여 한 줄에 출력한다. 빈 자리가 없으면 0 0을 출력한다.

10
1 0 0 2 0 0 1 0 0 2

2 2

6
0 0 1 0 0 0

4 3

4
2 1 2 1

0 0

출처: Devin.KR 자체 제작