같은 규격의 연속 생산

문제

한 공장의 생산 라인에서는 완성된 부품을 하나씩 검사한 뒤, 생산된 순서대로 기록한다. 각 부품에는 규격을 나타내는 정수 하나가 붙어 있다. 기록의 첫 번째 부품부터 마지막 부품까지의 위치에는 차례로 1번부터 N번까지 번호를 붙인다. 규격 번호가 같으면 같은 규격의 부품이며, 번호의 크기는 품질이나 생산 순위와 관계가 없다. 공장에서는 같은 규격의 부품이 연속해서 생산된 구간 하나를 골라 전시하려 한다. 전시할 구간은 시작 위치부터 끝 위치까지의 부품을 빠짐없이 포함해야 한다. 구간에 포함된 모든 부품의 규격 번호는 같아야 하며, 부품을 건너뛰거나 생산 순서를 바꾸어서는 안 된다. 같은 규격이 다른 위치에서 다시 등장하더라도, 그 사이에 다른 규격이 있으면 두 부분을 하나의 구간으로 합칠 수 없다. 전시 담당자는 조건을 만족하는 구간 중 부품 수가 가장 많은 구간을 선택한다. 부품 수가 같은 구간이 여러 개라면 시작 위치가 가장 작은 구간을 선택한다. 구간의 길이는 끝 위치에서 시작 위치를 뺀 값에 1을 더한 값이다. 길이가 1인 구간도 선택할 수 있으므로, 선택 가능한 구간은 항상 존재한다. 예를 들어 생산 기록의 일부가 4, 4, 7, 4라면, 앞의 두 부품은 길이 2인 구간으로 묶을 수 있다. 마지막 4를 앞의 두 부품과 함께 선택하는 것은 허용되지 않는다. 또한 선택한 구간의 바로 앞이나 뒤에 같은 규격이 있다면 그 부품까지 포함하여 더 긴 구간을 만들 수 있다. 생산 기록이 주어졌을 때 전시할 구간의 시작 위치와 길이를 구하는 프로그램을 작성하라. 기록은 원형으로 이어져 있지 않으며, 마지막 부품 다음에 첫 번째 부품이 이어진다고 생각해서는 안 된다.

입력

첫째 줄에 부품 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 생산 순서대로 규격 번호를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. (0 ≤ A_i ≤ 9)

출력

선택한 구간의 시작 위치와 길이를 공백으로 구분하여 한 줄에 출력한다. 시작 위치는 1부터 센다.

9
2 2 5 5 5 1 1 1 4

3 3

5
6 6 6 6 6

1 5

1
0

1 1

출처: Devin.KR 자체 제작