有 n 颗珍珠排成一排。让我们从左到右用 1 到 n 的整数来枚举它们。编号为 i 的珍珠的类型为 ai。
让我们将一系列连续的珍珠称为段。如果一个片段包含两颗相同类型的珍珠,我们称该片段为好片段。
将珍珠行拆分为最大数量的好片段。请注意,每颗珍珠都应恰好出现在分区的一个部分中。
由于输入/输出可能达到巨大的尺寸,建议使用快速输入/输出方法:例如,在C++中更喜欢使用scanf/printf而不是cin/cout,在Java中更喜欢使用BufferedReader/PrintWriter而不是Scanner/System.out。
输入
第一行包含整数 n (1 ≤ n ≤ 3·105) — 一行中珍珠的数量。
第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) – 第 i 颗珍珠的类型。
输出
在第一行打印整数 k — 行分区中的最大段数。
接下来的 k 行中的每一行都应包含两个整数 lj, rj (1 ≤ lj ≤ rj ≤ n) — 第 j 段中最左边和最右边珍珠的数量。
请注意,您应该打印珍珠行的正确分区,因此每颗珍珠都应该恰好位于一个段中,并且所有段都应包含两颗相同类型的珍珠。
如果有多个最优解,则打印其中任意一个。您可以按任何顺序打印片段。
如果该行没有正确的分区,则打印数字“-1”。
示例
输入 #1
5 1 2 3 4 1
输出 #1
1 1 5
输入 #2
5 1 2 3 4 5
输出 #2
-1
输入 #3
7 1 2 1 3 1 2 1
输出 #3
2 1 3 4 7