← 返回题目列表

Codeforces · 224/B

B. 数组

中文机器翻译题面 查看原题

你有一个数组 a,由 n 个整数组成:a1, a2, ..., an。您的任务是通过包含段 [l, r] (1 ≤ l ≤ r ≤ n) 找到一个最小值,使得在数字 al, al + 1, ..., ar 中恰好有 k 个不同的数字。

长度为 m = r - l + 1 的线段 [l, r](1 ≤ l ≤ r ≤ n;l, r 是整数),满足给定属性,如果没有满足该属性且长度小于 m 的线段 [x, y],则称为包含最小,使得 1 ≤ l ≤ x ≤ y ≤ r ≤ n。请注意,满足给定属性的段 [l, r] 不必是所有段中长度最小的。

输入

第一行包含两个空格分隔的整数:n 和 k (1 ≤ n, k ≤ 105)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an — 数组 a 的元素 (1 ≤ ai ≤ 105)。

输出

打印一对以空格分隔的整数 l 和 r (1 ≤ l ≤ r ≤ n),使得段 [l, r] 就是问题的答案。如果查找的段不存在,则打印“-1 -1”(不带引号)。如果有多个正确答案,请打印其中一个。

示例

输入 #1

4 2
1 2 2 3

输出 #1

1 2

输入 #2

8 3
1 1 2 2 3 3 4 5

输出 #2

2 5

输入 #3

7 4
4 7 7 4 7 4 7

输出 #3

-1 -1

注意

在数字 a1 和 a2 中的第一个样本中,恰好有两个不同的数字。

在第二个样本段 [2, 5] 中,是包含三个不同数字的最小包含段,但在这些段中,它的长度不是最小的。

在第三个示例中,不存在具有四个不同数字的段。