버스 안내판의 구간 선택

문제

한 지역의 버스 운영팀은 노선 안내판에 넣을 연속 구간을 고르고 있다. 버스는 정해진 순서대로 N개의 정류장을 지나며, 각 정류장에는 그 주변을 대표하는 시설 종류 번호가 하나씩 붙어 있다. 시설 종류 번호가 같은 정류장끼리는 안내판에서 같은 시설 설명을 함께 사용한다. 같은 종류의 시설이 노선의 여러 위치에 떨어져 있어도 종류 수를 셀 때는 하나로 센다. 안내판에는 시설 설명을 최대 K개까지 넣을 수 있다. 운영팀은 노선에서 시작 정류장과 끝 정류장을 하나씩 정하고, 그 사이의 모든 정류장을 빠짐없이 안내하려 한다. 따라서 선택한 구간은 원래 노선에서 연속해야 하며, 구간 안의 정류장을 임의로 빼거나 순서를 바꿀 수 없다. 선택한 구간에 등장하는 서로 다른 시설 종류의 수가 K 이하일 때만 그 구간을 안내판에 넣을 수 있다. 운영팀의 첫 번째 목표는 안내하는 정류장 수를 최대화하는 것이다. 정류장마다 시설 종류가 반복되어도 해당 정류장은 각각 길이에 포함한다. 같은 최대 길이를 만드는 구간이 여러 개라면 시작 정류장 번호가 가장 작은 구간을 선택한다. 구간의 길이와 시작 번호가 같으면 끝 번호도 같으므로 다른 동점 기준은 필요하지 않다. 정류장 번호는 버스가 방문하는 순서대로 1번부터 N번까지다. 시작 정류장과 끝 정류장도 선택한 구간에 포함하며, 정류장 하나만으로 이루어진 구간도 허용한다. K는 1 이상이므로 조건을 만족하는 구간은 항상 존재한다. 노선 전체에 등장하는 시설 종류가 K개보다 적어도 별도의 빈 설명을 채울 필요는 없다. 운영팀이 선택할 구간의 길이와 양 끝 정류장 번호를 구한다.

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. 1 ≤ K ≤ N ≤ 100,000이다.
둘째 줄에 각 정류장의 시설 종류 번호 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다. 각 A_i는 1 이상 99 이하의 정수다.

출력

선택한 구간의 길이, 시작 정류장 번호, 끝 정류장 번호를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 길이가 최대인 구간이 여러 개라면 시작 번호가 가장 작은 구간을 출력한다.

9 2
1 2 1 3 3 2 2 4 4

4 4 7

6 1
7 7 8 8 9 9

2 1 2

4 4
2 5 2 8

4 1 4

출처: Devin.KR 자체 제작