B. Расшифровка повторяшек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Оли есть массив целых чисел $$$a_1, a_2, \ldots, a_n$$$. Оля хочет разбить его на тандемные повторы. Так как это не всегда возможно, перед разбиением она хочет несколько (возможно, ноль) раз вставить в произвольное место пару одинаковых чисел. Помогите ей!

Более формально:

  • Тандемным повтором называется любая последовательность $$$x$$$ четной длины $$$2k$$$ такая, что для всех $$$1 \le i \le k$$$ выполнено, что $$$x_i = x_{i + k}$$$.
  • Массив $$$a$$$ разбивается на тандемные повторы, если его можно разбить на несколько частей, каждая из которых является тандемным повтором.
  • Оля может несколько раз выбрать произвольное целое число $$$c$$$ и вставить $$$[c, c]$$$ в произвольное место массива (в самом начале, между какими-то двумя числами, или в самом конце).
  • Вам необходимо сделать некоторое количество вставок и затем разбить массив на тандемные повторы, или сообщить, что это невозможно. Обратите внимание, что от вас не требуется минимизировать количество вставок.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится единственное целое число $$$t$$$ ($$$1 \le t \le 30\,000$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит единственное целое число $$$n$$$ ($$$1 \le n \le 500$$$) — изначальную длину массива.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — сам массив.

Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$250\,000$$$.

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

Для каждого набора входных данных выведите ответ в следующем формате.

Если операциями вставки двух равных чисел нельзя превратить массив в конкатенацию тандемных повторов, выведите единственное целое число $$$-1$$$.

Иначе выведите количество вставок $$$q$$$ ($$$0 \le q \le 2 \cdot n^2$$$) в вашем решении. Далее выведите описание вставок.

В каждой из следующих $$$q$$$ строк выведите два целых числа $$$p$$$ и $$$c$$$ ($$$1 \le c \le 10^9$$$), которые означают, что после $$$p$$$ чисел с начала массива вставляется число $$$c$$$ два раза подряд. Если перед этим действием длина массива была $$$m$$$, то должно быть выполнено $$$0 \le p \le m$$$.

Далее вам нужно вывести любое разбиение итогового массива на тандемные повторы. Сначала выведите целое число $$$d$$$, а на следующей строке выведите последовательность четных целых чисел $$$t_1, t_2, \ldots, t_d$$$ размера $$$d$$$ ($$$d, t_i \ge 1$$$). Это длины подотрезков, являющихся тандемными повторами, на которые можно разбить получившийся массив после всех операций.

Заметим, что после всех действий длина массива $$$a$$$ будет равна $$$m = n + 2 \cdot q$$$. Должны выполняться следующие условия:

  • $$$m = \sum\limits_{i = 1}^{d}{t_i}$$$.
  • Для всех целых $$$i$$$ таких, что $$$1 \le i \le d$$$, последовательность $$$a_l, a_{l+1}, \ldots, a_r$$$ является тандемным повтором, где $$$l = \sum\limits_{j = 1}^{i - 1}{t_j} + 1$$$, $$$r = l + t_i - 1$$$.

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

Пример
Входные данные
4
2
5 7
2
5 5
6
1 3 1 2 2 3
6
3 2 1 1 2 3
Выходные данные
-1
0
1
2
4
1 3
5 3
5 3
10 3
2
8 6 
5
0 3
8 3
5 3 
6 2 
7 1
4
2 6 6 2
Примечание

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

Во втором наборе входных данных массив уже является тандемным повтором $$$[5, 5] = \underbrace{([5] + [5])}_{t_1 = 2}$$$, поэтому мы можем не делать никаких вставок.

В третьем наборе входных данных у нас изначально следующий массив: $$$$$$[1, 3, 1, 2, 2, 3].$$$$$$ После первого действия вставки с $$$p = 1, c = 3$$$: $$$$$$[1, \textbf{3, 3}, 3, 1, 2, 2, 3].$$$$$$ После второго действия вставки с $$$p = 5, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, \textbf{3, 3}, 2, 2, 3].$$$$$$ После третьего действия вставки с $$$p = 5, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, \textbf{3, 3}, 3, 3, 2, 2, 3].$$$$$$ После четвертого действия вставки с $$$p = 10, c = 3$$$: $$$$$$[1, 3, 3, 3, 1, 3, 3, 3, 3, 2, \textbf{3, 3}, 2, 3].$$$$$$ Итоговый массив можно представить как конкатенацию двух тандемных повторов: $$$$$$\underbrace{([1, 3, 3, 3] + [1, 3, 3, 3])}_{t_1 = 8} + \underbrace{([3, 2, 3] + [3, 2, 3])}_{t_2 = 6}.$$$$$$

В четвёртом наборе входных данных у нас изначально следующий массив: $$$$$$[3, 2, 1, 1, 2, 3].$$$$$$ После первого действия вставки с $$$p = 0, c = 3$$$: $$$$$$[\textbf{3, 3}, 3, 2, 1, 1, 2, 3].$$$$$$ После второго действия вставки с $$$p = 8, c = 3$$$: $$$$$$[3, 3, 3, 2, 1, 1, 2, 3, \textbf{3, 3}].$$$$$$ После третьего действия вставки с $$$p = 5, c = 3$$$ $$$$$$[3, 3, 3, 2, 1, \textbf{3, 3}, 1, 2, 3, 3, 3].$$$$$$ После четвертого действия вставки с $$$p = 6, c = 2$$$: $$$$$$[3, 3, 3, 2, 1, 3, \textbf{2, 2}, 3, 1, 2, 3, 3, 3].$$$$$$ После пятого действия вставки с $$$p = 7, c = 1$$$: $$$$$$[3, 3, 3, 2, 1, 3, 2, \textbf{1, 1}, 2, 3, 1, 2, 3, 3, 3].$$$$$$ Итоговый массив можно представить как конкатенацию тандемных повторов: $$$$$$\underbrace{([3] + [3])}_{t_1 = 2} + \underbrace{([3, 2, 1] + [3, 2, 1])}_{t_2 = 6} + \underbrace{([1, 2, 3] + [1, 2, 3])}_{t_3 = 6} + \underbrace{([3] + [3])}_{t_4 = 2}.$$$$$$