천문대의 연속 관측 묶음

문제

한 천문대는 밤하늘을 일정한 시간 간격으로 촬영한다. 연구원은 한밤에 얻은 사진 N장을 촬영 시각 순서대로 정리했다. 각 사진에는 자동 분석기가 판정한 관측 대상의 종류가 하나씩 기록되어 있다. 종류는 0부터 9까지의 정수로 나타내며, 같은 번호는 같은 종류를 뜻한다. 사진의 번호는 촬영 순서대로 1부터 N까지다. 연구원은 여러 사진을 하나의 연속 관측 묶음으로 만들어 교육용 화면에 보여 주려 한다. 묶음은 시작 사진 L과 끝 사진 R을 정하여 L번부터 R번까지의 사진을 모두 포함한다. 이때 1 ≤ L ≤ R ≤ N이어야 한다. 중간 사진을 빼거나 사진의 순서를 바꿀 수 없다. 묶음의 길이는 포함된 사진 수인 R-L+1이다. 화면에는 관측 대상의 종류마다 별도의 설명 칸이 필요하다. 준비된 설명 칸은 K개이므로, 하나의 묶음에 등장하는 서로 다른 종류의 수는 K 이하여야 한다. 같은 종류의 사진이 여러 장 포함되어도 설명 칸은 하나만 사용한다. 사용하지 않는 설명 칸이 있어도 되므로 서로 다른 종류가 정확히 K개일 필요는 없다. 조건을 만족하는 묶음 중 길이가 가장 긴 것을 찾아라. 가장 긴 묶음이 여러 개라면 시작 사진 번호 L이 가장 작은 묶음을 선택한다. 선택한 묶음의 길이와 시작 사진 번호, 끝 사진 번호를 출력한다. K는 1 이상이므로 사진 한 장만 포함하는 묶음은 언제나 조건을 만족한다. 따라서 정답이 없는 경우는 없다. 전체 사진에 등장하는 종류가 K개 이하라면 사진 전체가 하나의 묶음이 될 수 있다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ N ≤ 200,000이고 1 ≤ K ≤ 10이다.
둘째 줄에 각 사진의 종류를 나타내는 N개의 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. 0 ≤ A_i ≤ 9이다.

출력

선택한 묶음의 길이, 시작 사진 번호 L, 끝 사진 번호 R을 공백으로 구분하여 한 줄에 출력한다. 최대 길이가 같으면 L이 가장 작은 묶음을 출력한다.

9 2
1 2 1 3 3 2 2 4 4

4 4 7

6 1
0 0 5 5 8 8

2 1 2

1 10
7

1 1 1

출처: Devin.KR 자체 제작