Вам задан массив из n элементов. Вам нужно превратить его во взаимнопростый массив за наименьшее количество действий.
За одно действие вы можете вставить любое положительное целое число, не превосходящее величины 109, в любое место массива.
Массив называется взаимнопростым, если любая пара соседних чисел взаимнопроста.
В теории чисел два числа a и b называются взаимнопростыми, если единственным положительным делителем обоих чисел является число 1.
Выходные данные
В первой строке выведите целое число k — наименьшее количество элементов, которые нужно добавить в массив a, чтобы он стал взаимнопростым.
Во второй строке выведите n + k целых чисел aj — элементы массива a после добавления k элементов. Обратите внимание, что этот массив должен быть взаимнопростым, то есть все пары соседних элементов должны быть взаимнопросты. Также новый массив должен быть получен из исходного массива a добавлением ровно k элементов.
Если существует несколько решений, выведите любое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 7 28
|
1
2 7 9 28
|