Co-prime Array

### 题目描述 ### 给你一个n个元素的数组，你必须尽可能少的添加元素使得该序列成为一个co-prime数组。 每次可以插入任何正整数不大于10^9在数组的任意位置。 如果一个数组的任意两个相邻的数是互质的，那么这个数组就是co-prime。 ### 输入输出格式 #### 输入格式： 第一行 n （1≤n≤1000） 第二行 ai的描述 (1≤ai≤10^9) #### 输出格式： 第一行输出k的值---k为添加到数组a中使其成为co-prime数组的最少添加元素个数 第二行应该包含n+k个整数a[i]的输出 如果有多个答案，输出任意一个就行

You are given an array of $ n $ elements, you must make it a co-prime array in as few moves as possible. In each move you can insert any positive integral number you want not greater than $ 10^{9} $ in any place in the array. An array is co-prime if any two adjacent numbers of it are co-prime. In the number theory, two integers $ a $ and $ b $ are said to be co-prime if the only positive integer that divides both of them is $ 1 $ .

The first line contains integer $ n $ ( $ 1<=n<=1000 $ ) — the number of elements in the given array. The second line contains $ n $ integers $ a_{i} $ ( $ 1<=a_{i}<=10^{9} $ ) — the elements of the array $ a $ .

Print integer $ k $ on the first line — the least number of elements needed to add to the array $ a $ to make it co-prime. The second line should contain $ n+k $ integers $ a_{j} $ — the elements of the array $ a $ after adding $ k $ elements to it. Note that the new array should be co-prime, so any two adjacent values should be co-prime. Also the new array should be got from the original array $ a $ by adding $ k $ elements to it. If there are multiple answers you can print any one of them.

3
2 7 28

1
2 7 9 28