CF660A Co-prime Array

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

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.