수족관 조명 띠

문제

한 수족관의 관람 통로에는 작은 수조 N개가 일렬로 놓여 있다. 수조에는 통로 입구에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 수조 위에는 조명이 하나씩 설치되어 있으며, 조명의 색은 색 번호를 나타내는 정수로 기록되어 있다. 같은 색 번호는 같은 색을 뜻하고, 서로 다른 색 번호는 서로 다른 색을 뜻한다. 수족관 관리자는 같은 색의 조명이 끊김 없이 이어지는 부분에 안내판을 설치하려고 한다. 안내판이 담당하는 구간은 연속한 수조로 이루어져야 하며, 그 구간에 있는 조명은 모두 같은 색이어야 한다. 떨어져 있는 수조들의 색이 같더라도 그 사이에 다른 색의 조명이 있으면 하나의 구간으로 묶을 수 없다. 수조 하나만으로 이루어진 구간도 조건을 만족한다. 관리자는 조건을 만족하는 구간 중 수조의 개수가 가장 많은 구간을 선택한다. 그러한 구간이 여러 개라면 시작 수조의 번호가 가장 작은 구간을 선택한다. 색 번호의 크기는 선택 우선순위에 영향을 주지 않는다. 선택한 구간의 시작 수조 번호와 구간에 포함된 수조의 개수를 알아내는 것이 목표다. 예를 들어 어느 색이 통로의 여러 위치에 등장하더라도 그 색의 전체 등장 횟수를 세는 것은 안내판의 길이를 정하는 기준이 아니다. 실제로 서로 이웃한 수조에서 같은 색이 연속해서 나타나는 길이만 비교한다. 또한 첫 수조나 마지막 수조를 포함하는 구간도 다른 구간과 똑같이 선택할 수 있다. 조명의 색을 바꾸거나 수조의 순서를 옮길 수는 없다. 입력에는 수조가 적어도 하나 있으므로 선택할 구간은 항상 존재한다. 주어진 색 번호 목록을 읽고 관리자가 선택할 구간을 구하는 프로그램을 작성한다.

입력

첫째 줄에 수조 수 N이 주어진다. 둘째 줄에 1번부터 N번 수조까지의 조명 색 번호 A1, A2, …, AN이 공백으로 구분되어 주어진다.
모든 입력값은 정수이다. 1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 100이다.

출력

선택한 구간의 시작 수조 번호와 수조 개수를 공백으로 구분하여 한 줄에 출력한다. 길이가 같은 구간이 여러 개라면 시작 수조 번호가 가장 작은 구간을 출력한다.

9
4 4 2 2 2 7 7 7 1

3 3

4
8 3 6 2

1 1

5
9 9 9 9 9

1 5

출처: Devin.KR 자체 제작