C. Жемчужинки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В ряд расположены n жемчужинок. Пронумеруем жемчужинки целыми числами от 1 до n слева направо. Жемчужинка номер i имеет тип ai.

Последовательность подряд идущих жемчужинок будем называть подотрезком. Подотрезок будем называть хорошим, если в нём есть пара жемчужинок одинакового типа.

Вам требуется разбить исходный ряд жемчужинок на наибольшее количество хороших подотрезков. Обратите внимание, что каждая жемчужинка должна попасть ровно в один подотрезок разбиения.

Рекомендуется для ввода и вывода данных использовать функции scanf, printf в языке C++, поскольку они работают значительно быстрее потоков cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 3·105) — количество жемчужинок в ряду.

Во второй строке находятся n целых чисел ai (1 ≤ ai ≤ 109) — тип i-й жемчужинки.

Выходные данные

В первой строке выведите целое число k — наибольшее количество подотрезков в разбиении ряда жемчужинок.

В каждой из следующих k строк выведите по два целых числа lj, rj (1 ≤ lj ≤ rj ≤ n) — номера самой левой и самой правой жемчужинки в j-м подотрезке.

Выведенный набор должен образовывать разбиение ряда жемчужинок на хорошие подотрезки, то есть каждая жемчужинка исходного ряда должна попасть ровно в один подотрезок и каждый подотрезок должен содержать пару жемчужинок одинакового типа.

Если существует несколько оптимальных решений вы можете вывести любое из них. Подотрезки можно выводить в любом порядке.

Если исходный ряд невозможно разбить на хорошие подотрезки, выведите одно число "-1".

Примеры
Входные данные
5
1 2 3 4 1
Выходные данные
1
1 5
Входные данные
5
1 2 3 4 5
Выходные данные
-1
Входные данные
7
1 2 1 3 1 2 1
Выходные данные
2
1 3
4 7