도서관의 한 분류 전시대

문제

한 도서관에는 책을 한 권씩 세울 수 있는 전시 칸이 일렬로 놓여 있다. 전시 칸에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있다. 각 칸은 비어 있거나 책 한 권을 담고 있으며, 책에는 1부터 9까지의 정수 중 하나인 분류 번호가 붙어 있다. 비어 있는 칸은 숫자 0으로 표시한다. 사서는 같은 분류의 책이 연속으로 놓인 부분에 안내 띠를 붙이려고 한다. 안내 띠는 연속한 전시 칸들을 덮어야 하며, 덮인 모든 칸에는 같은 분류 번호의 책이 있어야 한다. 빈 칸을 포함하거나 서로 다른 분류의 책을 함께 덮는 안내 띠는 사용할 수 없다. 책이 있는 칸 하나만 덮는 안내 띠는 사용할 수 있다. 이번에는 안내 띠를 최대 하나만 붙일 수 있다. 사서는 가능한 한 많은 칸을 덮는 안내 띠를 선택한다. 덮는 칸 수가 같은 후보가 여러 개라면, 시작하는 칸 번호가 가장 작은 후보를 선택한다. 전시 칸의 책을 옮기거나 빈 칸을 채울 수는 없으며, 떨어져 있는 두 구간을 하나의 안내 띠로 연결할 수도 없다. 예를 들어 분류 번호가 같은 책 세 권이 연속으로 놓여 있고 바로 다음 칸이 비어 있다면, 그 빈 칸을 넘어서 같은 분류의 책이 다시 나오더라도 앞의 세 권과 함께 덮을 수 없다. 또한 어떤 분류의 책이 전시대 전체에 많이 있더라도, 서로 떨어져 있다면 그 개수를 모두 더해 안내 띠의 길이로 삼을 수 없다. 전시대의 현재 상태가 배열로 주어진다. 선택한 안내 띠가 덮는 칸 수, 시작하는 칸 번호, 책의 분류 번호를 이 순서대로 구한다. 덮는 칸 수가 같은 경우에는 오직 시작 번호로만 우선순위를 정한다. 모든 칸이 비어 있다면 안내 띠를 붙이지 않으며, 세 값 모두 0으로 출력한다. 전시대에 책이 한 권이라도 있다면 반드시 안내 띠를 하나 선택한다.

입력

첫째 줄에 전시 칸 수인 정수 N이 주어진다.
둘째 줄에 각 칸의 상태를 나타내는 정수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 100,000이며, 모든 i에 대해 0 ≤ Aᵢ ≤ 9이다. Aᵢ가 0이면 빈 칸이고, 그렇지 않으면 해당 칸에 있는 책의 분류 번호이다.

출력

선택한 안내 띠가 덮는 칸 수, 시작하는 칸 번호, 책의 분류 번호를 공백으로 구분하여 한 줄에 출력한다. 모든 칸이 비어 있다면 0 0 0을 출력한다.

12
0 2 2 2 0 3 3 3 1 1 0 1

3 2 2

5
0 0 0 0 0

0 0 0

6
4 4 0 7 7 7

3 4 7

출처: Devin.KR 자체 제작