← 返回题目列表

Codeforces · 620/C

C. 珍珠连成一线

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

有 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