← 返回题目列表

Codeforces · 616/D

D. 最长的 k-Good 段

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

给出包含 n 个整数的数组 a。我们将一个或多个连续元素组成的序列称为段。如果该段包含不超过 k 个不同值,则我们将其称为 k-good。

找到任意最长的 k-good 段。

由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在C++中更喜欢使用scanf/printf而不是cin/cout,在Java中更喜欢使用BufferedReader/PrintWriter而不是Scanner/System.out。

输入

第一行包含两个整数 n, k (1 ≤ k ≤ n ≤ 5·105) — a 中的元素数量和参数 k。

第二行包含 n 个整数 ai (0 ≤ ai ≤ 106) — 数组 a 的元素。

输出

打印两个整数 l, r (1 ≤ l ≤ r ≤ n) — 某个 k 好最长段的左端索引和右端索引。如果有几个最长的段,您可以打印其中任何一个。 a中的元素从左到右编号为1到n。

示例

输入 #1

5 5
1 2 3 4 5

输出 #1

1 5

输入 #2

9 3
6 5 1 2 3 2 1 4 5

输出 #2

3 7

输入 #3

3 1
1 2 3

输出 #3

1 1