Educational Codeforces Round 6 |
---|
Закончено |
В ряд расположены 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
Название |
---|