같은 부품이 이어진 구간

문제

한 공장은 생산 라인을 따라 지나가는 부품의 종류 번호를 차례대로 기록한다. 기록 장치는 부품 하나가 지나갈 때마다 정수 하나를 배열의 맨 뒤에 추가한다. 하루의 기록이 끝나면 배열의 첫 번째 원소는 가장 먼저 지나간 부품을, 마지막 원소는 가장 나중에 지나간 부품을 뜻한다. 기록에서 부품을 삭제하거나 순서를 바꾸는 일은 없다. 담당자는 같은 종류의 부품이 끊기지 않고 생산된 구간 가운데 하나를 골라 포장 설비를 점검하려 한다. 점검 후보는 같은 종류 번호가 연속해서 나타나는 최대 구간이다. 여기서 최대 구간이란 양옆으로 같은 종류의 부품을 더 붙일 수 없는 구간을 뜻한다. 배열의 처음이나 끝에 닿는 구간도 후보가 되며, 길이가 1인 구간도 후보가 된다. 같은 종류가 여러 곳에서 나타나더라도 중간에 다른 종류가 하나라도 있으면 서로 다른 후보로 취급한다. 점검 후보를 고르는 기준은 다음과 같다. 먼저 부품 수가 가장 많은 후보를 고른다. 부품 수가 같은 후보가 여러 개이면 종류 번호가 가장 작은 후보를 고른다. 부품 수와 종류 번호가 모두 같으면 기록에서 시작 위치가 가장 앞선 후보를 고른다. 이 기준을 차례로 적용하면 선택되는 후보는 항상 하나이다. 기록의 위치는 1부터 시작한다. 선택한 후보의 종류 번호, 시작 위치, 부품 수를 순서대로 구해야 한다. 시작 위치는 선택한 구간의 첫 부품이 전체 기록에서 몇 번째인지를 뜻한다. 기록에는 적어도 하나의 부품이 있으므로 점검 후보가 없는 경우는 없다. 모든 부품의 종류가 같다면 기록 전체가 하나의 후보가 된다.

입력

첫째 줄에 부품 수 N이 주어진다. N은 1 이상 100,000 이하의 정수이다.
둘째 줄에 기록된 순서대로 종류 번호 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 1,000 이하의 정수이다.

출력

선택한 후보의 종류 번호, 시작 위치, 부품 수를 공백으로 구분하여 한 줄에 출력한다.

10
4 4 2 2 2 7 7 7 1 1

2 3 3

7
3 3 8 3 3 9 9

3 1 2

1
6

6 1 1

출처: Devin.KR 자체 제작