다양하게 듣는 짧은 구간

문제

음악 스트리밍 서비스는 한 이용자의 재생 기록에서 짧은 감상 구간을 골라 보여 주려고 한다. 재생 기록에는 곡의 식별 번호가 시간순으로 저장되어 있다. 같은 곡을 여러 번 들었다면 같은 번호가 여러 위치에 나타난다. 기록의 위치는 가장 오래된 것부터 1번, 2번, …, N번으로 매긴다. 감상 구간은 시작 위치 L과 끝 위치 R을 정하여 선택한다. 선택한 구간에는 L번부터 R번까지의 모든 기록이 포함되어야 하며, 중간의 기록을 빼거나 순서를 바꿀 수 없다. 구간의 길이는 재생 시간의 합이 아니라 포함된 기록의 개수인 R-L+1이다. 같은 곡이 여러 번 포함되어도 서로 다른 곡의 수를 셀 때에는 한 곡으로 센다. 서비스가 찾는 구간에는 서로 다른 곡이 적어도 K개 포함되어야 한다. 이 조건을 만족하는 모든 구간 중 길이가 가장 짧은 것을 선택한다. 가장 짧은 구간이 여러 개라면 시작 위치 L이 가장 작은 구간을 선택한다. 길이와 시작 위치가 같으면 끝 위치도 같으므로 추가적인 동점 규칙은 필요하지 않다. 예를 들어 어떤 구간의 곡 번호가 8, 8, 3이라면 길이는 3이고 서로 다른 곡의 수는 2다. 이 구간은 K가 2일 때 조건을 만족하지만 K가 3일 때에는 만족하지 않는다. 한 곡을 반복해서 들은 기록도 길이에는 모두 포함된다는 점에 주의한다. 전체 기록에 서로 다른 곡이 K개보다 적다면 조건을 만족하는 구간은 존재하지 않는다. 반대로 K가 1이라면 기록 하나만으로도 조건을 만족한다. 주어진 기록과 K에 대해 서비스가 선택할 구간의 양 끝 위치를 구한다. 기록의 맨 앞이나 맨 뒤를 포함하는 구간도 다른 구간과 똑같이 후보로 취급한다.

입력

첫 줄에 재생 기록 수 N과 필요한 서로 다른 곡의 수 K가 주어진다. 1≤N≤100,000, 1≤K≤100이다.
둘째 줄에 곡 번호 A_1, A_2, …, A_N이 공백으로 주어진다. 1≤A_i≤100이다. 모든 수는 정수다.

출력

선택한 구간의 시작 위치 L과 끝 위치 R을 공백으로 구분하여 출력한다. 조건을 만족하는 구간이 없으면 -1을 출력한다.

8 3
2 2 5 2 7 5 9 9

3 5

5 3
4 8 4 8 4

-1

4 1
7 7 2 3

1 1

출처: Devin.KR 자체 제작