수조 이름표의 긴 줄

문제

수족관의 전시실에는 작은 수조 N개가 일렬로 놓여 있다. 수조에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 수조의 이름표에는 그 수조에서 기르는 물고기의 종류를 나타내는 정수 하나가 적혀 있다. 종류 번호는 1 이상 9 이하이며, 같은 번호는 같은 종류를 뜻한다. 서로 다른 수조에 같은 종류의 물고기가 있어도 된다. 관리자는 방문객이 한 종류의 물고기를 연속해서 관찰할 수 있는 구간을 안내판에 표시하려 한다. 안내판에 표시할 구간은 왼쪽 끝 수조부터 오른쪽 끝 수조까지 빠짐없이 포함해야 하며, 그 안에 있는 모든 수조의 종류 번호가 같아야 한다. 구간의 길이는 포함된 수조의 개수이다. 중간에 다른 종류의 수조가 있다면 그 수조를 건너뛰어 하나의 구간으로 묶을 수 없다. 관리자는 조건을 만족하는 구간 중 길이가 가장 긴 구간을 선택한다. 길이가 가장 긴 구간이 여러 개라면 왼쪽 끝 수조의 번호가 가장 작은 구간을 선택한다. 물고기의 종류 번호가 작다는 이유로 다른 구간을 먼저 선택하지는 않는다. 수조 하나만으로 이루어진 구간도 조건을 만족하므로 선택할 구간은 항상 존재한다. 수조를 옮기거나 이름표를 바꾸는 작업은 하지 않는다. 또한 수조들은 원형으로 배치된 것이 아니므로 마지막 수조와 첫 번째 수조는 이웃하지 않는다. 입력으로 주어진 순서를 그대로 사용하여 관리자가 선택할 구간을 구해야 한다. 선택한 구간의 왼쪽 끝 번호, 오른쪽 끝 번호, 그리고 그 구간에 적힌 종류 번호를 순서대로 출력하는 프로그램을 작성한다.

입력

첫째 줄에 수조의 개수 N이 주어진다. N은 1 이상 100,000 이하의 정수이다.
둘째 줄에 왼쪽 수조부터 종류 번호 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 9 이하의 정수이다.

출력

선택한 구간의 왼쪽 끝 수조 번호, 오른쪽 끝 수조 번호, 종류 번호를 공백으로 구분하여 한 줄에 출력한다. 길이가 같은 구간이 여러 개라면 왼쪽 끝 번호가 가장 작은 구간을 출력한다.

9
2 2 5 5 5 3 3 3 1

3 5 5

1
7

1 1 7

5
4 4 4 4 4

1 5 4

출처: Devin.KR 자체 제작