서가의 연속 구간

문제

도서관에서는 반납된 책을 긴 임시 서가에 꽂아 둔다. 서가에는 왼쪽부터 오른쪽으로 N권의 책이 있으며, 각 책에는 분야를 나타내는 한 자리 정수 표지가 붙어 있다. 직원은 책을 옮기기 전에 같은 분야의 책이 연속으로 꽂힌 구간 하나를 골라 안내판을 설치하려 한다. 책의 순서는 이미 정해져 있으므로, 안내판을 설치하기 위해 책을 옮기거나 서로 자리를 바꾸지는 않는다. 선택할 수 있는 구간은 시작 위치부터 끝 위치까지의 모든 책이 같은 분야인 비어 있지 않은 연속 구간이다. 구간 안에 다른 분야의 책이 한 권이라도 있으면 선택할 수 없다. 같은 분야의 책이 서가의 서로 다른 곳에 나뉘어 있더라도 그 사이에 다른 책이 있다면 하나의 구간으로 합칠 수 없다. 또한 서가의 마지막 책과 첫 번째 책은 서로 이웃한 것으로 보지 않는다. 직원은 선택할 수 있는 구간 중 책의 수가 가장 많은 구간을 고른다. 책의 수가 같은 구간이 여러 개라면 시작 위치가 가장 작은 구간을 고른다. 분야 표지의 숫자가 작거나 큰지는 선택에 영향을 주지 않는다. 책의 위치는 왼쪽부터 1번, 2번, ..., N번으로 센다. 구간의 길이는 그 구간에 포함된 책의 수이며, 한 권만 있는 구간의 길이는 1이다. 예를 들어 같은 표지가 이어지다가 다른 표지가 나타나면 그 앞에서 하나의 연속 구간이 끝난다. 이후에 앞서 나온 표지가 다시 나타나도 새로운 구간으로 취급한다. 모든 책의 분야가 같다면 서가 전체를 고르고, 모든 이웃한 책의 분야가 다르다면 가장 왼쪽 책 한 권을 고른다. N은 1 이상이므로 선택할 수 있는 구간은 항상 존재한다. 직원이 고를 구간의 시작 위치, 길이, 분야 표지를 이 순서대로 구하는 프로그램을 작성한다.

입력

첫째 줄에 책의 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 왼쪽부터 각 책의 분야 표지를 나타내는 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. (0 ≤ A_i ≤ 9)

출력

선택한 구간의 시작 위치, 길이, 분야 표지를 공백으로 구분하여 한 줄에 출력한다. 가장 긴 구간이 여러 개면 시작 위치가 가장 작은 구간을 출력한다.

10
2 2 7 7 7 1 1 1 4 4

3 3 7

1
0

1 1 0

6
5 5 5 5 5 5

1 6 5

출처: Devin.KR 자체 제작