给出包含 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