한 번에 소개할 원두

문제

카페에서는 하루 동안 판매한 커피의 원두 번호를 주문 순서대로 기록한다. 주문 하나에는 원두 번호 하나가 대응하며, 같은 원두를 사용한 주문은 같은 번호를 가진다. 원두 번호의 크기는 맛이나 판매 순위를 뜻하지 않는다. 주문 기록에는 1번부터 N번까지 차례대로 번호가 붙어 있다. 매장 담당자는 이 기록의 연속한 일부를 골라 시음 행사 안내판에 소개하려 한다. 안내판에는 서로 다른 원두를 최대 K종류까지 설명할 수 있다. 따라서 선택한 구간에 등장하는 서로 다른 원두 번호의 개수가 K 이하여야 한다. 같은 원두가 구간 안에서 여러 번 등장하더라도 원두 종류는 하나로 센다. 구간 중간의 주문을 제외하거나 주문 순서를 바꿀 수 없으며, 양 끝 주문을 포함한 모든 주문을 선택해야 한다. 담당자는 조건을 만족하면서 주문 수가 가장 많은 구간을 원한다. 주문 수가 같은 구간이 여러 개라면 시작 주문 번호가 가장 작은 구간을 선택한다. 시작 번호까지 같은 두 구간은 길이가 같으므로 끝 번호도 같다. 선택한 구간의 주문 수, 시작 주문 번호, 끝 주문 번호를 구해야 한다. 예를 들어 한 구간의 원두 번호가 8, 3, 8이라면 주문은 세 개이지만 원두는 두 종류다. 이 구간은 K가 2 이상일 때 선택할 수 있다. 반면 앞뒤에 같은 원두가 있더라도 중간에 다른 원두가 있으면 그 원두도 반드시 종류 수에 포함한다. N과 K는 모두 1 이상이므로 주문 하나만 고르면 항상 조건을 만족한다. 따라서 선택 가능한 구간이 없는 경우는 주어지지 않는다.

입력

첫째 줄에 정수 N과 K가 공백으로 주어진다. 1 ≤ N ≤ 200,000, 1 ≤ K ≤ N이다.
둘째 줄에 주문 순서대로 원두 번호를 나타내는 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 1 ≤ A_i ≤ 1,000,000,000이다.

출력

선택한 구간의 주문 수, 시작 주문 번호, 끝 주문 번호를 공백으로 구분하여 한 줄에 출력한다. 주문 번호는 1부터 시작한다. 최대 길이의 구간이 여러 개라면 시작 주문 번호가 가장 작은 구간을 출력한다.

8 2
4 7 4 9 9 7 7 2

4 4 7

5 1
6 6 3 3 8

2 1 2

1 1
1000000000

1 1 1

출처: Devin.KR 자체 제작