В ряд расположены n жемчужинок. Пронумеруем жемчужинки целыми числами от 1 до n слева направо. Жемчужинка номер i имеет тип ai.
Последовательность подряд идущих жемчужинок будем называть подотрезком. Подотрезок будем называть хорошим, если в нём есть пара жемчужинок одинакового типа.
Вам требуется разбить исходный ряд жемчужинок на наибольшее количество хороших подотрезков. Обратите внимание, что каждая жемчужинка должна попасть ровно в один подотрезок разбиения.
Рекомендуется для ввода и вывода данных использовать функции scanf, printf в языке C++, поскольку они работают значительно быстрее потоков cin, cout. Аналогично, рекомендуется использовать классы BufferedReader, PrintWriter вместо Scanner, System.out в языке Java.
Выходные данные
В первой строке выведите целое число k — наибольшее количество подотрезков в разбиении ряда жемчужинок.
В каждой из следующих k строк выведите по два целых числа lj, rj (1 ≤ lj ≤ rj ≤ n) — номера самой левой и самой правой жемчужинки в j-м подотрезке.
Выведенный набор должен образовывать разбиение ряда жемчужинок на хорошие подотрезки, то есть каждая жемчужинка исходного ряда должна попасть ровно в один подотрезок и каждый подотрезок должен содержать пару жемчужинок одинакового типа.
Если существует несколько оптимальных решений вы можете вывести любое из них. Подотрезки можно выводить в любом порядке.
Если исходный ряд невозможно разбить на хорошие подотрезки, выведите одно число "-1".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 2 3 4 1
|
1
1 5
|
|
2
|
5
1 2 3 4 5
|
-1
|
|
3
|
7
1 2 1 3 1 2 1
|
2
1 3
4 7
|