Выходные данные
Для каждого набора входных данных выведите ответ в следующем формате.
Если операциями вставки двух равных чисел нельзя превратить массив в конкатенацию тандемных повторов, выведите единственное целое число \(-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\).
Можно показать, что если решение существует, то существует решение, которое удовлетворяет заданным ограничениям. Если существует несколько возможных ответов, вы можете вывести любой.
Примечание
В первом наборе входных данных невозможно вставками двух равных чисел подряд массив, который является конкатенацией тандемных повторов.
Во втором наборе входных данных массив уже является тандемным повтором \([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}.\(\)