나란히 놓인 캠핑 자리

문제

캠핑장에는 일렬로 놓인 N개의 자리가 있다. 자리는 입구에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있다. 관리인은 각 자리에 설치된 바닥판의 종류를 한 자리 정수로 기록했다. 같은 숫자는 같은 종류의 바닥판을 뜻하며, 숫자의 크기에는 다른 의미가 없다. 모든 자리에는 바닥판이 정확히 하나씩 설치되어 있다. 관리인은 같은 종류의 바닥판으로 이어진 구역 하나를 골라 단체 손님에게 안내하려 한다. 안내할 구역은 시작 자리부터 끝 자리까지 빠짐없이 포함하는 연속한 구간이어야 한다. 그 구간에 포함된 모든 자리의 바닥판 종류가 같아야 하며, 중간에 다른 종류의 자리가 하나라도 있으면 하나의 구역으로 안내할 수 없다. 서로 떨어진 두 구역의 바닥판 종류가 같더라도 두 구역을 합칠 수 없다. 조건을 만족하는 구역 중 포함된 자리 수가 가장 많은 구역을 선택한다. 가장 많은 자리 수를 가진 구역이 여러 개이면 시작 자리 번호가 가장 작은 구역을 선택한다. 선택한 구역의 길이와 시작 자리 번호, 끝 자리 번호를 구하는 프로그램을 작성한다. 자리의 순서와 바닥판 종류를 바꾸는 작업은 허용되지 않는다. 한 자리만 포함하는 구간도 조건을 만족한다. 따라서 입력에 자리가 하나 이상 주어지면 선택할 구역은 항상 존재한다. 모든 자리의 바닥판 종류가 서로 이웃한 자리와 다르다면 가장 먼저 있는 한 자리를 선택한다. 반대로 모든 자리의 종류가 같다면 전체 자리를 하나의 구역으로 선택한다. 출력하는 자리 번호는 입력에서의 위치를 기준으로 하며, 첫 번째 위치의 번호는 1이다.

입력

첫째 줄에 자리 수를 나타내는 정수 N이 주어진다. (1 ≤ N ≤ 100,000)
둘째 줄에 각 자리의 바닥판 종류를 나타내는 정수 A_1, A_2, ..., A_N이 순서대로 주어진다. (0 ≤ A_i ≤ 9)

출력

선택한 구역의 길이, 시작 자리 번호, 끝 자리 번호를 공백으로 구분하여 한 줄에 출력한다. 길이가 같으면 시작 자리 번호가 가장 작은 구역을 출력한다.

9
2 2 7 7 7 1 1 1 4

3 3 5

1
0

1 1 1

5
4 4 4 4 4

5 1 5

출처: Devin.KR 자체 제작