원형 관측 기록판

문제

산마루 천문대에는 관측 순서를 표시하는 원형 기록판이 있다. 기록판에는 N개의 칸이 있으며, 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. 각 칸에는 그 순서에 관측할 하늘 구역의 번호가 하나 적혀 있다. 하늘 구역 번호는 1 이상 99 이하의 정수다. N번 칸 다음에는 다시 1번 칸이 이어진다. 관측 담당자는 망원경의 방향을 바꾸지 않고 처리할 수 있는 구간을 찾아 표시하려 한다. 표시할 구간은 시작 칸 하나와 길이 하나로 정한다. 시작 칸부터 시계 방향으로 길이만큼의 칸을 차례대로 읽었을 때, 모든 칸에 적힌 하늘 구역 번호가 같아야 한다. 구간의 길이는 1 이상 N 이하의 정수이며, 하나의 구간에서 같은 칸을 두 번 읽을 수 없다. 따라서 기록판을 여러 바퀴 돌아 구간의 길이를 늘리는 것은 허용되지 않는다. 가능한 구간 중 길이가 가장 긴 구간을 선택한다. 가장 긴 구간이 여러 개라면 하늘 구역 번호가 가장 작은 구간을 선택한다. 길이와 하늘 구역 번호가 모두 같다면 시작 칸의 번호가 가장 작은 구간을 선택한다. 시작 칸의 번호는 입력에 주어진 원래 번호를 사용하며, 기록판을 돌려서 새 번호를 붙이지 않는다. 예를 들어 마지막 두 칸과 처음 세 칸에 같은 번호가 적혀 있다면, 이 다섯 칸은 경계를 지나 이어지는 하나의 구간이 될 수 있다. 또한 모든 칸에 같은 번호가 적혀 있다면 길이 N인 구간을 어느 칸에서나 시작할 수 있으므로, 동점 규칙에 따라 1번 칸에서 시작하는 구간을 선택한다. N은 항상 1 이상이므로 선택할 수 있는 구간은 반드시 존재한다. 선택한 구간의 하늘 구역 번호, 시작 칸 번호, 길이를 구하는 프로그램을 작성한다.

입력

첫째 줄에 칸의 수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
둘째 줄에 1번 칸부터 N번 칸까지 적힌 하늘 구역 번호 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 99 이하의 정수다.

출력

선택한 구간의 하늘 구역 번호, 시작 칸 번호, 길이를 순서대로 공백으로 구분하여 한 줄에 출력한다.

8
4 4 7 7 7 2 4 4

4 7 4

10
8 8 3 3 6 6 3 3 9 9

3 3 2

4
12 12 12 12

12 1 4

출처: Devin.KR 자체 제작