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.


-----Input-----

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.


-----Output-----

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.


-----Example-----
Input
3
2 7 28

Output
1
2 7 9 28

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Number theory

Implementation

Greedy algorithms


Solutions:
import math
from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
cnt = 0
ans = []
for i in range(n - 1):
	ans.append(a[i])
	if gcd(a[i], a[i + 1]) > 1:
		ans.append(1)
		cnt += 1
ans.append(a[-1])
print(cnt)
print(*ans)


import fractions
n = int(input())
A = [int(x) for x in input().split()]
B = []
for i in range(n - 1):
	B.append(A[i])
	if fractions.gcd(A[i], A[i + 1]) != 1:
		B.append(1)
B.append(A[-1])
print(len(B) - n)
print(' '.join(map(str, B)))


from collections import deque, defaultdict, Counter
from itertools import product, groupby, permutations, combinations
from math import gcd, floor, inf, log2, sqrt, log10
from bisect import bisect_right, bisect_left
from statistics import mode
from string import ascii_uppercase
lists = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197}
num = int(input())
arr = list(map(int, input().split()))
cnt = 0
ans = [arr[0]]
for i in range(1, num):
	if gcd(arr[i - 1], arr[i]) != 1:
		cnt += 1
		for d in lists:
			if gcd(arr[i - 1], d) == 1 and gcd(arr[i], d) == 1:
				dif = d
				break
		ans.append(dif)
	ans.append(arr[i])
print(cnt)
print(*ans)


from fractions import gcd
try:
	while True:
		n = int(input())
		a = list(map(int, input().split()))
		result = [a[0]]
		for x in a[1:]:
			if gcd(x, result[-1]) != 1:
				result.append(1)
			result.append(x)
		print(len(result) - len(a))
		print(' '.join(map(str, result)))
except EOFError:
	pass


import math
x = int(input())
y = list(map(int, input().split()))
count = 0
l = [y[0]]
for i in range(1, len(y)):
	if math.gcd(y[i - 1], y[i]) != 1:
		count += 1
		l.append(1)
		l.append(y[i])
		continue
	l.append(y[i])
print(count)
for k in l:
	print(k, end=' ')
print()


n = int(input())
a = list(map(int, input().split()))

def nod(a, b):
	while a != 0 and b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b
prime_a = [a[0]]
count = 0
for i in range(n - 1):
	if nod(a[i], a[i + 1]) != 1:
		prime_a.append(1)
		count += 1
	prime_a.append(a[i + 1])
print(count)
print(*prime_a)


from math import sqrt

def co_prime(v1, v2):
	t = v1 % v2
	if t == 0:
		return (v2 == 1, v2)
	while True:
		(v1, v2) = (v2, t)
		if v1 % v2:
			t = v1 % v2
		else:
			ans = v2
			break
	return (ans == 1, ans)
n = int(input())
a = list(map(int, input().split()))
aux = [0] * n
res = []
k = 0
for i in range(n - 1):
	temp = co_prime(a[i], a[i + 1])
	if temp[0]:
		continue
	else:
		T = int(sqrt(temp[1]))
		while True:
			if co_prime(a[i], T)[0] and co_prime(T, a[i + 1])[0]:
				break
			T += 1
		aux[i] = T
		k += 1
for i in range(n):
	res.append(a[i])
	if aux[i]:
		res.append(aux[i])
print(k)
print(' '.join(map(str, res)))


from math import gcd
n = int(input())
s = [int(i) for i in input().split()] + [1]
d = []
for i in range(n):
	d.append(s[i])
	if gcd(s[i], s[i + 1]) != 1:
		d.append(1)
print(len(d) - len(s) + 1)
print(*d)


import re
import sys
from bisect import bisect, bisect_left, insort, insort_left
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from itertools import accumulate, combinations, combinations_with_replacement, groupby, permutations, product
from math import acos, asin, atan, ceil, cos, degrees, factorial, gcd, hypot, log2, pi, radians, sin, sqrt, tan
from operator import itemgetter, mul
from string import ascii_lowercase, ascii_uppercase, digits

def inp():
	return int(input())

def inlist():
	return list(map(int, input().split()))

def instr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
n = inp()
a = inlist()
b = []
b.append(a[0])
c = 0
for i in range(1, n):
	if gcd(b[-1], a[i]) != 1:
		b.append(1)
		b.append(a[i])
		c += 1
	else:
		b.append(a[i])
print(c)
print(*b)


from math import gcd
n = int(input())
coprime_array = list(map(int, input().split()))
pairs = []
for i in range(1, n):
	if gcd(coprime_array[i], coprime_array[i - 1]) > 1:
		pairs.append(i - 1)
print(len(pairs))
answer = ''
for i in range(n):
	answer += str(coprime_array[i]) + ' '
	if len(pairs) and i == pairs[0]:
		answer += '1 '
		del pairs[0]
print(answer)


import math
n = int(input())
a = list(map(int, input().split()))
l = []
l.append(a[0])
for i in range(1, n):
	if math.gcd(a[i], a[i - 1]) == 1:
		l.append(a[i])
	else:
		l.append(1)
		l.append(a[i])
print(len(l) - len(a))
print(*l)


def gcd(x, y):
	if x < y:
		t = x
		x = y
		y = t
	if x % y == 0:
		return y
	else:
		return gcd(y, x % y)
n = int(input())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
b = [a[0]]
k = 0
for i in range(1, n):
	if gcd(a[i - 1], a[i]) != 1:
		b.append(1)
		k += 1
	b.append(a[i])
s = str(b[0])
for i in range(1, len(b)):
	s += ' ' + str(b[i])
print(k)
print(s)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def main():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [a[0]]
	for i in range(1, n):
		if gcd(a[i - 1], a[i]) != 1:
			b.append(1)
		b.append(a[i])
	print(len(b) - n)
	print(' '.join(map(str, b)))
main()


import math
n = int(input())
sequence = list(map(int, input().split()))
i = 0
count = 0
while i < len(sequence) - 1:
	if math.gcd(sequence[i], sequence[i + 1]) != 1:
		sequence.insert(i + 1, 1)
		count += 1
	i += 1
print(count)
print(' '.join(map(str, sequence)))


import sys
import math
import itertools
import collections

def ii():
	return int(input())

def mi():
	return map(int, input().split())

def li():
	return list(map(int, input().split()))

def lcm(a, b):
	return abs(a * b) // math.gcd(a, b)

def wr(arr):
	return ' '.join(map(str, arr))

def revn(n):
	return str(n)[::-1]

def dd():
	return collections.defaultdict(int)

def ddl():
	return collections.defaultdict(list)

def sieve(n):
	if n < 2:
		return list()
	prime = [True for _ in range(n + 1)]
	p = 3
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 2
	r = [2]
	for p in range(3, n + 1, 2):
		if prime[p]:
			r.append(p)
	return r

def divs(n, start=1):
	r = []
	for i in range(start, int(math.sqrt(n) + 1)):
		if n % i == 0:
			if n / i == i:
				r.append(i)
			else:
				r.extend([i, n // i])
	return r

def divn(n, primes):
	divs_number = 1
	for i in primes:
		if n == 1:
			return divs_number
		t = 1
		while n % i == 0:
			t += 1
			n //= i
		divs_number *= t

def prime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n <= 1:
		return False
	sqr = int(math.sqrt(n)) + 1
	for d in range(3, sqr, 2):
		if n % d == 0:
			return False
	return True

def convn(number, base):
	newnumber = 0
	while number > 0:
		newnumber += number % base
		number //= base
	return newnumber

def cdiv(n, k):
	return n // k + (n % k != 0)
n = ii()
a = li()
ans = []
k = 0
for i in range(n - 1):
	if math.gcd(a[i], a[i + 1]) != 1:
		ans += [a[i]] + [1]
		k += 1
	else:
		ans += [a[i]]
ans += [a[-1]]
print(k)
print(wr(ans))


import math
num_de_elementos = int(input())
elementos = list(map(int, input().split())) + [1]
aux = []
cont = 0
for i in range(num_de_elementos):
	aux.append(elementos[i])
	if math.gcd(elementos[i], elementos[i + 1]) != 1:
		aux.append(1)
		cont += 1
co_primos = ''
for i in aux:
	co_primos += str(i) + ' '
print(cont)
print(co_primos)


n = int(input())
a = [int(x) for x in input().split()]
l = []
ans = 0

def gcd(a, b):
	if a == 1 or b == 1:
		return 1
	if a == 0 or b == 0:
		return 0
	if a > b:
		a = a % b
		return gcd(a, b)
	else:
		b = b % a
		return gcd(a, b)
for i in range(0, n - 1):
	l.append(a[i])
	if gcd(a[i], a[i + 1]) != 1:
		l.append(1)
		ans += 1
l.append(a[n - 1])
print(ans)
for i in l:
	print(i, end=' ')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def __starting_point():
	n = int(input())
	A = list(map(int, input().split()))
	(ans, cnt) = ([A[0]], 0)
	for i in range(1, n):
		if gcd(A[i], A[i - 1]) != 1:
			ans.append(1)
			cnt += 1
		ans.append(A[i])
	print(cnt)
	print(' '.join((str(i) for i in ans)))
__starting_point()


from math import gcd
n = int(input())
x = list(map(int, input().split()))
s = ''
count = 0
for i in range(n - 1):
	s += str(x[i]) + ' '
	if gcd(x[i], x[i + 1]) != 1:
		count += 1
		s += '1 '
s += str(x[-1])
print(count)
print(s.rstrip())


def nod(a, b):
	while a != 0 and b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b
n = int(input())
m = list(map(int, input().split()))
k = [m[len(m) - 1]] * (2 * len(m))
k[0] = m[0]
l = 0
for i in range(n - 1):
	k[i + l] = m[i]
	if nod(m[i], m[i + 1]) != 1:
		l += 1
		k.insert(i + l, 1)
k = k[:len(m) + l]
print(l)
print(' '.join(map(str, k)))


import math
n = int(input())
ar = list(map(int, input().split()))
a = []
c = 0
for i in range(len(ar) - 1):
	a += [ar[i]]
	if math.gcd(ar[i], ar[i + 1]) > 1:
		a += [1]
		c += 1
a += [ar[-1]]
print(c)
print(*a)


import math
n = int(input())
a = list(map(int, input().strip().split()))
res = []
if n == 1:
	print(0)
	print(a[0])
else:
	c = 0
	for i in range(n - 1):
		g = math.gcd(a[i], a[i + 1])
		if g == 1:
			res.append(a[i])
		else:
			res.append(a[i])
			res.append(1)
			c += 1
	res.append(a[-1])
	print(c)
	print(' '.join(map(str, res)))


import math
n = int(input())
a = [int(i) for i in input().split()]
count = 0
ind = n - 1
while ind > 0:
	if math.gcd(a[ind], a[ind - 1]) != 1:
		count += 1
		a.insert(ind, 1)
	ind -= 1
print(count)
print(' '.join([str(i) for i in a]))


n = int(input())
val = list(map(int, input().split()))
res = [val[0]]
from fractions import gcd
for i in range(1, n):
	if gcd(val[i], val[i - 1]) > 1:
		res.append(1)
		res.append(val[i])
	else:
		res.append(val[i])
print(len(res) - len(val))
print(*res)


def mp():
	return map(int, input().split())

def lt():
	return list(map(int, input().split()))

def pt(x):
	print(x)

def ip():
	return input()

def it():
	return int(input())

def sl(x):
	return [t for t in x]

def spl(x):
	return x.split()

def aj(liste, item):
	liste.append(item)

def bin(x):
	return '{0:b}'.format(x)
n = it()
L = lt()

def gcd(x, y):
	if x % y == 0:
		return y
	else:
		return gcd(y, x % y)
c = 0
i = 0
while i + 1 < len(L):
	d = gcd(L[i], L[i + 1])
	if d != 1:
		L.insert(i + 1, 1)
		c += 1
	i += 1
print(c)
print(' '.join([str(x) for x in L]))


from math import gcd
n = int(input())
if n == 1:
	print(0)
	print(input())
	exit(0)
li = [int(i) for i in input().split()]
i = 0
p = 0
while True:
	if gcd(li[i], li[i + 1]) != 1:
		li.insert(i + 1, 1)
		p += 1
		i += 1
	else:
		i += 1
	if i == len(li) - 1:
		break
print(p)
print(*li)


n = int(input())
p = [int(x) for x in input().split()]

def gcd(a, b):
	if a < b:
		return gcd(b, a)
	elif b == 0:
		return a
	else:
		return gcd(b, a % b)
r = []
r.append(p[0])
for i in range(1, n):
	if gcd(p[i], p[i - 1]) > 1:
		r.append(1)
	r.append(p[i])
print(len(r) - len(p))
print(str.join(' ', map(str, r)))


n = int(input())
a = [int(s) for s in input().split()]

def evklid(a, b):
	while a != 0 and b != 0:
		if a > b:
			a = a % b
		else:
			b = b % a
	return a + b
s = ''
k = 0
s += str(a[0])
for i in range(1, n):
	if evklid(a[i], a[i - 1]) != 1:
		k += 1
		s += ' 1 ' + str(a[i])
	else:
		s += ' ' + str(a[i])
print(k)
print(s)


def nod(a, b):
	while a != 0 and b != 0:
		(a, b) = (max(a, b), min(a, b))
		a = a % b
	return a + b

def mynod(a, b):
	for i in range(2, a + b * 2):
		if nod(a, i) == 1 and nod(i, b) == 1:
			return i
ans = []
k = 0
n = int(input()) + 1
lis = list(map(int, input().split()))
lis.append(1)
for i in range(n - 1):
	if nod(lis[i], lis[i + 1]) != 1:
		ans.append(lis[i])
		ans.append(mynod(lis[i], lis[i + 1]))
		k += 1
	else:
		ans.append(lis[i])
print(k)
print(' '.join(map(str, ans)), end='\r\n')


import io, os
import sys
from math import gcd
from random import randint
from atexit import register
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
tokens = []
tokens_next = 0

def nextStr():
	global tokens, tokens_next
	while tokens_next >= len(tokens):
		tokens = input().split()
		tokens_next = 0
	tokens_next += 1
	return tokens[tokens_next - 1]

def nextInt():
	return int(nextStr())

def nextIntArr(n):
	return [nextInt() for i in range(n)]

def print(s, end='\n'):
	sys.stdout.write((str(s) + end).encode())
n = nextInt()
a = nextIntArr(n)
res = []
for i in range(n):
	if i == 0:
		res.append(a[i])
		continue
	if gcd(a[i], a[i - 1]) != 1:
		res.append(1)
	res.append(a[i])
print(len(res) - n)
print(' '.join(map(str, res)))


n = int(input())
A = list(map(int, input().split()))
import math

def sieve(n):
	ass = []
	is_prime = [True] * (n + 1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(math.sqrt(n)) + 1):
		if not is_prime[i]:
			continue
		for j in range(i * 2, n + 1, i):
			is_prime[j] = False
	for i in range(n + 1):
		if is_prime[i]:
			ass.append(i)
	return ass
S = sieve(1000)
k = 0
ans = []
import math
for i in range(n - 1):
	if math.gcd(A[i], A[i + 1]) != 1:
		for j in S:
			if math.gcd(A[i], j) == 1 and math.gcd(A[i + 1], j) == 1:
				ans.append(A[i])
				ans.append(j)
				k += 1
				break
	else:
		ans.append(A[i])
else:
	ans.append(A[n - 1])
print(k)
print(*ans)


import sys
import pprint

def parse_input():
	input()
	return list(map(int, input().split(' ')))

def solve(array):
	result = [array[0]]
	num_of_additions = 0
	for number in array[1:]:
		if gcd(number, result[-1]) != 1:
			result.append(1)
		result.append(number)
	print(len(result) - len(array))
	for num in result:
		print(num, end=' ')

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
solve(parse_input())


import math
num = int(input())
s = input()
array = []
array2 = []
counter = 0
for i in s.split():
	array.append(int(i))
for i in range(len(array) - 1):
	if math.gcd(array[i], array[i + 1]) > 1:
		array2.append(array[i])
		array2.append(1)
		counter += 1
	else:
		array2.append(array[i])
array2.append(array[len(array) - 1])
print(counter)
for i in array2:
	print(i, end=' ')


p = 10 ** 5
from math import gcd

def calc(a, b):
	prms = [2, 3, 5, 7, 11, 13]
	for i in prms:
		if gcd(i, a) == 1 and gcd(i, b) == 1:
			return i

def calc1(a):
	prms = [2, 3, 5, 7]
	for i in prms:
		if gcd(i, a) == 1:
			return i
n = int(input())
l = [int(i) for i in input().split()]
cnt = 0
l1 = []
for i in range(0, len(l) - 1):
	if gcd(l[i], l[i + 1]) != 1:
		l1.append(1)
		cnt += 1
print(cnt)
for i in range(0, n - 1):
	if gcd(l[i], l[i + 1]) != 1:
		print(l[i], end=' ')
		print(1, end=' ')
	else:
		print(l[i], end=' ')
print(l[n - 1])


from fractions import gcd

def is_co_prime(x, y):
	return gcd(x, y) != 1

def solve():
	N = int(input())
	L = list(map(int, input().split()))
	ans = [str(L[0])]
	x = 0
	for i in range(1, N):
		if is_co_prime(L[i], L[i - 1]):
			x += 1
			ans.append('1')
		ans.append(str(L[i]))
	print(x)
	print(' '.join(ans))
solve()


def mdc(a, b):
	if a == 0:
		return b
	else:
		return mdc(b % a, a)

def is_coprime(a, b):
	return mdc(a, b) == 1
import math
limit = int(math.sqrt(10 ** 9))
numbers = list(range(2, limit))
for i in range(0, int(math.sqrt(limit))):
	if numbers[i] > 0:
		k = 2
		while k * numbers[i] - 2 < len(numbers):
			numbers[numbers[i] * k - 2] = 0
			k += 1
primes = []
for n in numbers:
	if n > 0:
		primes.append(n)

def calc_coprime(a, b):
	i = 0
	while not is_coprime(primes[i], a) or not is_coprime(primes[i], b):
		i += 1
	return primes[i]
k = int(input())
nums = list(map(int, input().split(' ')))
result = []
result.append(nums[0])
for i in range(1, len(nums)):
	while not is_coprime(nums[i], result[-1]):
		result.append(calc_coprime(result[-1], nums[i]))
	result.append(nums[i])
print(len(result) - len(nums))
for n in result:
	print(n, end=' ')
print('')


from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
prev = a[0]
k = 0
for c in a[1:]:
	if gcd(prev, c) != 1:
		k += 1
	prev = c
print(k)
prev = a[0]
for c in a[1:]:
	print(prev, end=' ')
	if gcd(prev, c) != 1:
		print(1, end=' ')
	prev = c
print(prev)


import math
import logging

class CF660a(object):
	prime_numbers_set = set()
	prime_numbers_list = list()
	count = 0

	def __init__(self):
		self.log = logging.getLogger('CF660a')
		super(CF660a, self).__init__()

	def is_prime(self, number):
		limit = int(math.sqrt(number)) + 1
		for i in range(1, len(self.prime_numbers_list)):
			n = self.prime_numbers_list[i]
			if n >= limit:
				break
			if number % n == 0:
				return False
		return True

	def init_primes(self, upper=10 ** 9):
		limit = int(math.sqrt(upper)) + 2
		self.prime_numbers_set = set(range(3, limit, 2))
		self.prime_numbers_set.add(2)
		self.prime_numbers_list = [1, 2]
		for i in range(3, limit, 2):
			if i in self.prime_numbers_set:
				self.prime_numbers_set.difference_update(range(i + i, limit, i))
		self.prime_numbers_list = sorted(self.prime_numbers_set)

	def prime_divisors(self, number):
		self.log.debug('looking for divisors for %d', number)
		divisors = {1, number}
		if number in self.prime_numbers_set:
			self.log.debug('the number is prime')
			return divisors
		for prime in self.prime_numbers_list:
			if prime > number:
				self.log.debug("don't check upper bound %d", prime)
				break
			if number % prime == 0:
				self.log.debug('found prime divisor %d', prime)
				divisors.add(prime)
				self.log.debug('found also adding result %d', number / prime)
				divisors.add(number / prime)
		return divisors

	def process(self, numbers):
		prev_divisors = {1}
		for number in numbers:
			divisors = self.prime_divisors(number)
			if divisors.intersection(prev_divisors) != {1}:
				self.count += 1
				yield 1
				yield number
			else:
				yield number
			prev_divisors = divisors

def main():
	in_count = input()
	in_numbers = map(int, input().split())
	solution = CF660a()
	solution.init_primes()
	result = list(map(str, solution.process(in_numbers)))
	print(solution.count)
	print(' '.join(result))
main()


int_inp = lambda : int(input())
strng = lambda : input().strip()
strl = lambda : list(input().strip())
mul = lambda : map(int, input().split())
mulf = lambda : map(float, input().split())
seq = lambda : list(map(int, input().split()))
import math
from collections import Counter, defaultdict
k = int_inp()
m = seq()
a = [m[0]]
for i in range(1, k):
	if math.gcd(m[i], m[i - 1]) != 1:
		a.append(1)
	a.append(m[i])
print(len(a) - k)
print(*a)


def gcd(n1, n2):
	if n1 == 0:
		return n2
	return gcd(n2 % n1, n1)
n = int(input())
seq = list(map(int, input().split()))
k = 0
for e in range(len(seq) - 1, 0, -1):
	if gcd(seq[e], seq[e - 1]) != 1:
		k += 1
		seq.insert(e, 1)
print(k)
for i in seq:
	print(i, end=' ')


def mdc(dividendo, divisor):
	if divisor == 0:
		return dividendo
	else:
		return mdc(divisor, dividendo % divisor)

def main(args):
	n = int(input())
	entrada = list(map(int, input().split()))
	saida = []
	saida.append(entrada[0])
	count = 0
	for i in range(1, n):
		if mdc(entrada[i - 1], entrada[i]) == 1:
			saida.append(entrada[i])
		else:
			count += 1
			saida.append(1)
			saida.append(entrada[i])
	print(count)
	result = ''
	result += str(saida[0])
	for j in range(1, len(saida)):
		result += ' ' + str(saida[j])
	print(result)
	return 0
import sys
sys.exit(main(sys.argv))


def gcd(a, b):
	if a < b:
		(a, b) = (b, a)
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
arr = [int(x) for x in input().split()]
ans = []
alterations = 0
for i in range(n):
	ans.append(arr[i])
	if i + 1 < n and gcd(arr[i], arr[i + 1]) > 1:
		ans.append(1)
		alterations += 1
print(alterations)
for el in ans:
	print(el, end=' ')


import math

def function(n, nums):
	if n == 1:
		print(0)
		print(*nums)
	if n > 1:
		c = 0
		total = 0
		ind = []
		for i in range(1, len(nums)):
			if math.gcd(nums[i], nums[i - 1]) != 1:
				ind.append(i)
		if len(ind) > 0:
			for i1 in range(len(ind)):
				ind[total] += c
				nums.insert(ind[total], 1)
				total += 1
				c += 1
		print(total)
		print(*nums)
n = int(input())
nums = list(map(int, input().rstrip().split()))
function(n, nums)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input())
a = list(map(int, input().split()))
k = [i for i in range(n - 1) if gcd(a[i], a[i + 1]) > 1]
for (i, x) in enumerate(k):
	a.insert(x + i + 1, 1)
print(len(k))
print(*a)


def gcd(a, b):
	return gcd(b, a % b) if b > 0 else a
n = int(input())
A = [int(a) for a in input().split()]
B = [0] * (2 * n - 1)
j = 0
for i in range(n - 1):
	B[j] = A[i]
	j += 1
	if gcd(A[i], A[i + 1]) > 1:
		B[j] = 1
		j += 1
B[j] = A[n - 1]
print(j - n + 1)
for i in range(j + 1):
	print(B[i], end=' ')


import math
n = int(input())
a = list(map(int, input().split()))
resp = []
count = 0
for i in range(len(a) - 1):
	if math.gcd(a[i], a[i + 1]) == 1:
		resp.append(a[i])
		count += 1
	else:
		resp.append(a[i])
		count += 1
		resp.append(1)
		count += 1
resp.append(a[n - 1])
count += 1
print(count - n)
for j in range(len(resp) - 1):
	print(resp[j])
print(resp[count - 1])


import sys
import bisect
from bisect import bisect_left as lb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)

def hnbhai():
	n = sb()
	a = sd()
	ans = [a[0]]
	for i in range(1, n):
		if gcd(a[i], a[i - 1]) != 1:
			ans.append(1299709)
			ans.append(a[i])
		else:
			ans.append(a[i])
	print(len(ans) - n)
	print(*ans)
for _ in range(1):
	hnbhai()


import math
L = lambda : list(map(int, input().split()))
M = lambda : map(int, input().split())
I = lambda : int(input())
n = I()
a = L()
b = []
x = 0
for i in range(n - 1):
	b.append(a[i])
	if math.gcd(a[i], a[i + 1]) > 1:
		b.append(1)
		x += 1
b.append(a[-1])
print(x)
print(*b)


from math import gcd
n = int(input())
arr = list(map(int, input().split()))
ans = []
cnt = 0
for i in range(n - 1):
	if gcd(arr[i], arr[i + 1]) > 1:
		ans.append(arr[i])
		ans.append(1)
		cnt += 1
	else:
		ans.append(arr[i])
ans.append(arr[-1])
print(cnt)
print(*ans)


import math

def sieve(n):
	(primes, is_prime) = ([2], [True] * (n >> 1))
	for i in range(3, n, 2):
		cover = i * i
		if cover > n:
			for j in range(i, n, 2):
				if is_prime[j >> 1]:
					primes.append(j)
			break
		elif is_prime[i >> 1]:
			primes.append(i)
			jump = i << 1
			for j in range(cover, n, jump):
				is_prime[j >> 1] = False
	return primes
n = int(input().rstrip())
a = list(map(int, input().rstrip().split()))
primes = sieve(100000)
res = [a[0]]
cnt = 0
for i in range(1, len(a)):
	if math.gcd(a[i - 1], a[i]) != 1:
		for prime in primes:
			if a[i - 1] % prime != 0 and a[i] % prime != 0:
				res.append(prime)
				cnt += 1
				break
	res.append(a[i])
print(cnt)
print(' '.join(map(str, res)))


gcd = lambda a, b: a if b == 0 else gcd(b, a % b)

def f(l):
	n = len(l)
	nl = [l[0]]
	i = 0
	while i < n - 1:
		(a, b) = (l[i], l[i + 1])
		g = gcd(a, b) if a > b else gcd(b, a)
		if g > 1:
			nl.append(1)
		nl.append(l[i + 1])
		i += 1
	return [[len(nl) - n], nl]
_ = int(input())
l = list(map(int, input().split()))
[print(*r) for r in f(l)]


def gcd(a, b):
	while b != 0:
		t = b
		b = a % b
		a = t
	return a

def coprime(a, b):
	if gcd(a, b) == 1:
		return True
	else:
		return False

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def find_coprime(a, b, primelist):
	for p in primelist:
		if coprime(p, a) and coprime(p, b):
			return p
	n = len(primelist)
	p = primelist[n - 1] + 2
	while True:
		if not isPrime(p):
			p += 2
		primelist.append(p)
		if coprime(p, a) and coprime(p, b):
			return p
		p += 2
	return p

def coprime_array(a, b, primelist):
	n = len(a)
	k = 0
	if n == 1:
		b.append(a[0])
		return k
	for i in range(n):
		if i == n - 1:
			b.append(a[i])
			break
		b.append(a[i])
		if not coprime(a[i], a[i + 1]):
			b.append(find_coprime(a[i], a[i + 1], primelist))
			k += 1
	return k
n = int(input())
a = [int(x) for x in input().split()]
primelist = [2, 3, 5, 7]
b = []
k = coprime_array(a, b, primelist)
print(k)
print(*b, sep=' ')


n = int(input())
l = list(map(int, input().split()))

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
ls = []
c = 0
for i in range(n - 1):
	ls.append(l[i])
	if gcd(l[i], l[i + 1]) != 1:
		c += 1
		ls.append(1)
ls.append(l[n - 1])
print(c)
print(*ls)


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
a = list(map(int, input().split(' ')))
c = 0
for i in range(n - 1, 0, -1):
	if a[i] != 1 and a[i - 1] != 1 and (gcd(a[i], a[i - 1]) != 1):
		a.insert(i, 1)
		c += 1
print(c)
for j in a:
	print(j, end=' ')


import math
n = int(input())
mas = [int(c) for c in input().split()]
l = []
m = mas[0]
for i in range(n - 1):
	if math.gcd(mas[i], mas[i + 1]) != 1:
		l.append(i + 1)
for i in l[::-1]:
	mas.insert(i, 1)
k = len(mas) - n
print(k)
for i in mas:
	print(i, end=' ')


from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
ans = []
for i in range(n):
	ans.append(a[i])
	if i + 1 < n and gcd(a[i], a[i + 1]) > 1:
		ans.append(1)
print(len(ans) - n)
for i in range(len(ans)):
	print(ans[i], end=' ')


def gcd(a, b):
	if b % a == 0:
		return a
	return gcd(b % a, a)
n = int(input())
arr = list(map(int, input().split()))
m = [arr[0]]
cnt = 0
for i in range(1, n):
	if arr[i] != 1 and arr[i] == arr[i - 1] or gcd(max(arr[i], arr[i - 1]), min(arr[i], arr[i - 1])) != 1:
		m.append(1)
		cnt += 1
		m.append(arr[i])
	else:
		m.append(arr[i])
print(cnt)
print(' '.join(map(str, m)))


t = 1
from math import gcd

def solve():
	n = int(input())
	l = list(map(int, input().split()))
	r = [l[0]]
	c = 0
	for i in range(1, n):
		if gcd(l[i], r[-1]) != 1:
			c += 1
			r.append(1)
			r.append(l[i])
		else:
			r.append(l[i])
	print(c)
	return r
while t:
	t -= 1
	print(*solve())


import sys
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 998244353
n = ii()
a = il()
ans = []
for i in range(n - 1):
	ans.append(a[i])
	if gcd(a[i], a[i + 1]) != 1:
		ans.append(1)
ans.append(a[n - 1])
print(len(ans) - n)
print(*ans)


from math import gcd
n = int(input())
arr = list(map(int, input().split(' ')))
arr2 = []
for i in range(len(arr) - 1):
	if not gcd(arr[i], arr[i + 1]) == 1:
		arr2.append(str(arr[i]))
		arr2.append(str(1))
	else:
		arr2.append(str(arr[i]))
arr2.append(str(arr[-1]))
print(len(arr2) - len(arr))
print(' '.join(arr2))


def gcd(a, b):
	while b:
		a %= b
		(a, b) = (b, a)
	return a
n = int(input())
l = list(map(int, input().split()))
k = 0
l1 = [l[0]]
for i in range(1, n):
	if gcd(l[i], l[i - 1]) == 1:
		l1.append(l[i])
	else:
		k += 1
		l1.append(1)
		l1.append(l[i])
print(k)
print(*l1)


def ehcoprimo(a, b):
	if a > b:
		x = a
		y = b
	else:
		x = b
		y = a
	while True:
		r = x % y
		if r != 0:
			x = y
			y = r
		if r == 0:
			break
	if y == 1:
		return True
	else:
		return False
n = int(input())
entrada = input().split()
entrada = [int(x) for x in entrada]
cont = 0
i = 0
while i < len(entrada) - 1:
	if not ehcoprimo(entrada[i], entrada[i + 1]):
		entrada.append(0)
		for j in range(len(entrada) - 1, i, -1):
			entrada[j] = entrada[j - 1]
		entrada[i + 1] = 1
		i += 1
		cont += 1
	i += 1
print(cont)
print(*entrada)


from math import *
n = int(input())
l = list(map(int, input().split()))
c = 0
d = []
for i in range(n - 1):
	if gcd(l[i], l[i + 1]) != 1:
		d.append(l[i])
		d.append(1)
		c += 1
	else:
		d.append(l[i])
d.append(l[-1])
print(c)
print(*d)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
new = [a[0]]
for i in range(1, n):
	if gcd(a[i], a[i - 1]) != 1:
		new.append(1)
	new.append(a[i])
print(len(new) - n)
print(*new)


n = int(input())
a = [int(i) for i in input().split()]
c = 0
i = 0
while i < n - 1:
	x = a[i]
	y = a[i + 1]
	while y > 0:
		(x, y) = (y, x % y)
	if x > 1:
		a = a[:i + 1] + [1] + a[i + 1:]
		i += 2
		c += 1
		n += 1
	else:
		i += 1
print(c)
print(*a)


def GCD(a, b):
	if a == 0:
		return b
	return GCD(b % a, a)
n = int(input())
a = [int(x) for x in input().split()]
resp = []
cont = 0
resp.append(a[0])
for i in range(1, n):
	if GCD(a[i - 1], a[i]) != 1:
		resp.append(1)
		cont += 1
	resp.append(a[i])
print(cont)
for e in resp:
	print(e, end=' ')


import sys, math, io, os, time, itertools, collections
mod = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(10000)
i = sys.stdin.readline
p = sys.stdout.write
global start, end

def isin(l, x):
	left = 0
	right = len(l) - 1
	if x < l[0]:
		return -1
	while left <= right:
		mid = left + (right - left) // 2
		if l[mid] == x:
			return mid
		elif l[mid] < x:
			ans = mid
			left = mid + 1
		else:
			right = mid - 1
	return ans

def ispal(l):
	n = len(l)
	for i in range(n // 2 + 1):
		if l[i] != l[n - i - 1]:
			return False
	return True

def ccarray(l):
	d = {l[k]: k for k in range(len(l))}
	m = sorted(d)
	return [d[m[k]] for k in range(len(l))]

def is_prime(n):
	if n <= 3:
		return n > 1
	if n % 2 == 0 or n % 3 == 0:
		return False
	k = 5
	while k ** 2 <= n:
		if n % k == 0 or n % (k + 2) == 0:
			return False
		k += 6
	return True

def sieve(n):
	prime = [True for k in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for k in range(p * p, n + 1, p):
				prime[k] = False
		p += 1

def main():
	n = int(i())
	a = deque([int(k) for k in i().split()])
	fin = [a.popleft()]
	count = 0
	while a:
		if math.gcd(fin[-1], a[0]) != 1:
			fin.append(1)
			count += 1
			fin.append(a.popleft())
		else:
			fin.append(a.popleft())
	p(str(count) + '\n')
	print(*fin)
t = 1
start = time.perf_counter()
for _ in range(t):
	main()
end = time.perf_counter()


n = int(input())
mass = list(map(int, input().split()))

def gcd(a, b):
	if b:
		return gcd(b, a % b)
	else:
		return a
i = 0
c = len(mass)
count = 0
while i < c - 1:
	k = gcd(mass[i], mass[i + 1])
	if k == 1:
		i += 1
		continue
	else:
		count += 1
		mass.insert(i + 1, 1)
		c += 1
		i += 2
print(count)
print(' '.join(map(str, mass)))


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
p = int(input())
b = list(map(int, input().split()))
z = 0
q = []
q.append(b[0])
for i in range(len(b) - 1):
	if gcd(b[i], b[i + 1]) != 1:
		q.append(1)
		z = z + 1
	q.append(b[i + 1])
print(z)
for i in range(len(q)):
	print(q[i], end=' ')


def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
n = int(input())
l = list(map(int, input().split()))
ans = ''
ans += str(l[0])
prev = l[0]
cnt = int(0)
for i in range(1, n):
	if gcd(prev, l[i]) != 1:
		prev = l[i]
		ans = ans + ' 1 ' + str(l[i])
		cnt += 1
	else:
		prev = l[i]
		ans = ans + ' ' + str(l[i])
print(cnt)
print(ans)


from math import *
sInt = lambda : int(input())
mInt = lambda : map(int, input().split())
lInt = lambda : list(map(int, input().split()))
n = sInt()
a = lInt()
i = 0
ans = 0
while i < n + ans - 1:
	if gcd(a[i], a[i + 1]) != 1:
		ans += 1
		a.insert(i + 1, 1)
		i += 1
	i += 1
print(ans)
print(*a, sep=' ')


def nod(a, b):
	while a * b:
		if a > b:
			a %= b
		else:
			b %= a
	return a + b
n = int(input())
l = [int(j) for j in input().split()]
g = [l[0]]
k = 0
for i in range(1, n):
	a = l[i - 1]
	b = l[i]
	if nod(a, b) != 1:
		k += 1
		g.append(1)
	g.append(b)
print(k)
print(*g)


import math, sys

def gcd(x, y):
	if y == 0:
		return x
	else:
		return gcd(y, x % y)
n = int(input())
a = list(map(int, input().split(' ')))
i = 1
if len(a) == 1:
	print(0)
	print(a[0])
	sys.exit()
while i < len(a):
	if gcd(max(a[i], a[i - 1]), min(a[i], a[i - 1])) > 1:
		a.insert(i, 1)
	i += 1
print(len(a) - n)
a = map(str, a)
print(' '.join(a))


from fractions import gcd
n = int(input())
count = 0
ip = list(map(int, input().split()))
op = [ip[0]]
if n == 1:
	print(0)
	print(ip[0])
else:
	for i in range(n - 1):
		if gcd(ip[i], ip[i + 1]) != 1:
			for j in range(2, 100000000):
				if gcd(ip[i], j) == 1 and gcd(ip[i + 1], j) == 1:
					op.append(j)
					op.append(ip[i + 1])
					count += 1
					break
		else:
			op.append(ip[i + 1])
	print(count)
	for i in op:
		print(i, end=' ')


from collections import deque as de
import math
import re
from collections import Counter as cnt
from functools import reduce
from typing import MutableMapping
from itertools import groupby as gb
from fractions import Fraction as fr
from bisect import bisect_left as bl, bisect_right as br

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

class My_stack:

	def __init__(self):
		self.data = []

	def my_push(self, x):
		return self.data.append(x)

	def my_pop(self):
		return self.data.pop()

	def my_peak(self):
		return self.data[-1]

	def my_contains(self, x):
		return self.data.count(x)

	def my_show_all(self):
		return self.data

	def isEmpty(self):
		return len(self.data) == 0
arrStack = My_stack()

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binarytodecimal(n):
	return int(n, 2)

def isPrime(n):
	if n <= 1:
		return False
	if n <= 3:
		return True
	if n % 2 == 0 or n % 3 == 0:
		return False
	i = 5
	while i * i <= n:
		if n % i == 0 or n % (i + 2) == 0:
			return False
		i = i + 6
	return True

def get_prime_factors(number):
	prime_factors = []
	while number % 2 == 0:
		prime_factors.append(2)
		number = number / 2
	for i in range(3, int(math.sqrt(number)) + 1, 2):
		while number % i == 0:
			prime_factors.append(int(i))
			number = number / i
	if number > 2:
		prime_factors.append(int(number))
	return prime_factors

def get_frequency(list):
	dic = {}
	for ele in list:
		if ele in dic:
			dic[ele] += 1
		else:
			dic[ele] = 1
	return dic

def Log2(x):
	return math.log10(x) / math.log10(2)

def getProduct(n):
	product = 1
	while n != 0:
		product = product * (n % 10)
		n = n // 10
	return product

def dupconscount(nums):
	element = []
	freque = []
	if not nums:
		return element
	running_count = 1
	for i in range(len(nums) - 1):
		if nums[i] == nums[i + 1]:
			running_count += 1
		else:
			freque.append(running_count)
			element.append(nums[i])
			running_count = 1
	freque.append(running_count)
	element.append(nums[i + 1])
	return (element, freque)

def isPowerOfTwo(n):
	return math.ceil(Log2(n)) == math.floor(Log2(n))

def ceildiv(x, y):
	return (x + y - 1) // y

def di():
	return map(int, input().split())

def ii():
	return int(input())

def li():
	return list(map(int, input().split()))

def si():
	return list(map(str, input()))
n = ii()
a = li()
ans = []
for i in range(n - 1):
	ans.append(a[i])
	if math.gcd(a[i], a[i + 1]) != 1:
		ans.append(1)
ans.append(a[n - 1])
print(len(ans) - n)
print(*ans)


import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))

def main():
	ans_ = []
	primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
	n = int(input())
	arr = read()
	k = 0
	for i in range(n - 1):
		if gcd(arr[i], arr[i + 1]) != 1:
			ans_.append(arr[i])
			ans_.append(1)
			k += 1
		else:
			ans_.append(arr[i])
	ans_.append(arr[-1])
	print(k)
	print(*ans_)
main()


from sys import stdin
from math import gcd
n = int(input())
l = list(map(int, stdin.readline().split()))
t = []
for i in range(n - 1):
	t.append(l[i])
	if gcd(l[i], l[i + 1]) != 1:
		a = 0
		while a < l[i]:
			a += 1
			if gcd(a, l[i]) == 1:
				t.append(a)
				break
t.append(l[n - 1])
print(abs(n - len(t)))
print(' '.join(map(str, t)))


n = int(input())
A = list(map(int, input().split()))
import math
k = 0
ans = []
import math
for i in range(n - 1):
	if math.gcd(A[i], A[i + 1]) != 1:
		ans.append(A[i])
		ans.append(1)
		k += 1
	else:
		ans.append(A[i])
else:
	ans.append(A[n - 1])
print(k)
print(*ans)


def mcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a
n = int(input())
arr = [int(x) for x in input().split()]
t = 0
o = []
for i in range(len(arr) - 1):
	o.append(arr[i])
	if mcd(arr[i], arr[i + 1]) != 1:
		t += 1
		o.append(1)
o.append(arr[-1])
print(t)
print(' '.join([str(x) for x in o]))


import sys
import math
import collections
from pprint import pprint as pp
mod = 998244353
MAX = 10 ** 15

def inp():
	return map(int, input().split())

def array():
	return list(map(int, input().split()))

def vector(size, val=0):
	vec = [val for i in range(size)]
	return vec

def matrix(rowNum, colNum, val=0):
	mat = []
	for i in range(rowNum):
		collumn = [val for j in range(colNum)]
		mat.append(collumn)
	return mat
n = int(input())
a = array()
k = 0
ans = []
for i in range(n - 1):
	ans.append(a[i])
	if math.gcd(a[i], a[i + 1]) != 1:
		ans.append(1)
		k += 1
ans.append(a[-1])
print(k)
for i in ans:
	print(i, end=' ')


import math
n = int(input())
a = list(map(int, input().split()))
count = 0
ans = []
for i in range(n - 1):
	ans.append(a[i])
	if math.gcd(a[i], a[i + 1]) != 1:
		count += 1
		ans.append(1)
ans.append(a[-1])
print(count)
print(*ans)


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
n = int(input())
Ar = [int(x) for x in input().split()]
cnt = 0
A = []
for i in range(n - 1):
	if gcd(Ar[i], Ar[i + 1]) > 1:
		cnt += 1
		m = 1
		A.append(Ar[i])
		A.append(m)
	else:
		A.append(Ar[i])
A.append(Ar[-1])
print(cnt)
for i in A:
	print(i, end=' ')


def mdc(a, b):
	if a == 0:
		return b
	return mdc(b % a, a)
n = int(input())
a = list(map(int, input().split()))
res = []
for i in range(0, n - 1):
	(x, y) = (a[i], a[i + 1])
	res.append(x)
	if mdc(x, y) != 1:
		res.append(1)
res.append(a[n - 1])
print(len(res) - len(a))
for i in res:
	print(i, end=' ')
print()


def gcd(a, b):
	if a > b:
		(a, b) = (b, a)
	c = b % a
	while c != 0:
		(a, b) = (c, a)
		c = b % a
	return a
n = int(input())
num = list(map(int, input().split()))
l = n - 1
cnt = 0
newNum = []
for i in range(l):
	newNum.append(num[i])
	if gcd(num[i], num[i + 1]) != 1:
		newNum.append(1)
		cnt += 1
newNum.append(num[n - 1])
print(cnt)
for num in newNum:
	print(num, end=' ')


import sys
import math
import bisect

def solve(A):
	n = len(A)
	B = []
	for i in range(n):
		if i == 0:
			B.append(A[i])
		elif math.gcd(B[-1], A[i]) != 1:
			B.append(1)
			B.append(A[i])
		else:
			B.append(A[i])
	return B

def main():
	n = int(input())
	A = list(map(int, input().split()))
	B = solve(A)
	print('%d' % (len(B) - len(A)))
	print(' '.join(list((str(a) for a in B))))
main()


def hcf(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
n = int(input())
count = 0
lis = list(map(int, input().split()))
nlis = lis[:]
if len(lis) >= 2:
	j = 0
	for i in range(len(lis) - 1):
		if hcf(lis[i], lis[i + 1]) != 1:
			if count == 0:
				nlis = lis[:i]
				j = i
			count += 1
			nlis = nlis + lis[j:i + 1]
			nlis.append(1)
			j = i + 1
	if count == 0:
		nlis = []
	nlis = nlis + lis[j:]
print(count)
print(*nlis)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math

def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1)

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x

def binary_search(li, val, lb, ub):
	ans = 0
	while lb <= ub:
		mid = (lb + ub) // 2
		if li[mid] > val:
			ub = mid - 1
		elif val > li[mid]:
			lb = mid + 1
		else:
			ans = 1
			break
	return ans
from math import *
n = int(input())
numbers = list(map(int, input().split()))
ans = ''
cnt = 0
for i in range(1, n):
	if gcd(numbers[i], numbers[i - 1]) == 1:
		ans += str(numbers[i - 1]) + ' '
	else:
		cnt += 1
		ans += str(numbers[i - 1]) + ' 1 '
ans += str(numbers[-1])
print(cnt)
print(ans)


def prost(a, b):
	(a, b) = (max(a, b), min(a, b))
	while b != 0:
		a = a % b
		(a, b) = (b, a)
	if a == 1:
		return 0
	else:
		return 1
n = int(input())
s = input().split()
k = 0
for i in range(len(s) - 1):
	if prost(int(s[i]), int(s[i + 1])) == 1:
		s[i] = s[i] + ' ' + '1'
		k = k + 1
print(k)
print(' '.join((x for x in s)))


from sys import stdin, stdout
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import *
input = stdin.readline
prin = stdout.write
from random import sample
from collections import Counter, deque
from math import sqrt, ceil, log2, gcd
mod = 10 ** 9 + 7

def f(arr, i, j, d, dist):
	if i == j:
		return
	nn = max(arr[i:j])
	for tl in range(i, j):
		if arr[tl] == nn:
			dist[tl] = d
			f(arr, i, tl, d + 1, dist)
			f(arr, tl + 1, j, d + 1, dist)

def ps(n):
	cp = 0
	lk = 0
	arr = {}
	while n % 2 == 0:
		n = n // 2
		lk += 1
	arr[2] = lk
	for ps in range(3, ceil(sqrt(n)) + 1, 2):
		lk = 0
		while n % ps == 0:
			n = n // ps
			arr.append(n)
			arr.append(ps ** (lk + 1))
			lk += 1
		arr[ps] = lk
	if n != 1:
		lk += 1
		arr[n] = lk
	return arr

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def factorials(n, r):
	slr = n
	dpr = r
	qlr = 1
	qs = 1
	mod = 10 ** 9 + 7
	for ip in range(n - r + 1, n + 1):
		qlr = qlr * ip % mod
	for ij in range(1, r + 1):
		qs = qs * ij % mod
	ans = qlr * modInverse(qs) % mod
	return ans

def modInverse(b):
	qr = 10 ** 9 + 7
	return pow(b, qr - 2, qr)
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func

def power(arr):
	listrep = arr
	subsets = []
	for i in range(2 ** len(listrep)):
		subset = []
		for k in range(len(listrep)):
			if i & 1 << k:
				subset.append(listrep[k])
		subsets.append(subset)
	return subsets

def pda(n):
	list = []
	for i in range(1, int(sqrt(n) + 1)):
		if n % i == 0:
			if n // i == i:
				list.append(i)
			else:
				list.append(n // i)
				list.append(i)
	return list

def dis(xa, ya, xb, yb):
	return sqrt((xa - xb) ** 2 + (ya - yb) ** 2)

def ii():
	return int(input())

def ilist():
	return [int(x) for x in input().strip().split()]

def out(array: list) -> str:
	array = [str(x) for x in array]
	return ' '.join(array)

def islist():
	return list(map(str, input().split().rstrip()))

def outfast(arr: list) -> str:
	ss = ''
	for ip in arr:
		ss += str(ip) + ' '
	return prin(ss)
t = 1
for jj in range(t):
	n = ii()
	arr = ilist()
	ans = []
	cc = 0
	for i in range(n):
		if i + 1 < n and gcd(arr[i], arr[i + 1]) != 1:
			ans.append(arr[i])
			ans.append(1)
			cc += 1
		else:
			ans.append(arr[i])
	print(cc)
	print(out(ans))


n = int(input())
l = list(map(int, input().split()))
ans = [str(l[0])]

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
for i in range(1, n):
	if gcd(l[i], l[i - 1]) > 1:
		ans += ['1']
	ans += [str(l[i])]
print(len(ans) - n)
print(' '.join(ans))


n = int(input())
numbers = iter(map(int, input().split()))
from math import gcd
insert_counter = 0
b = next(numbers)
result = [b]
for _ in range(n - 1):
	a = b
	b = next(numbers)
	if gcd(a, b) != 1:
		insert_counter += 1
		result.append(1)
	result.append(b)
print(insert_counter)
[print(number, end=' ') for number in result]


import math

def divis(numero):
	divisores = set()
	for i in range(1, int(math.sqrt(numero)) + 1):
		if numero % i == 0:
			divisores.add(i)
			divisores.add(int(numero / i))
	return divisores
placebo = input()
numeros = list(map(int, input().split(' ')))
new_numeros = [str(numeros[0])]
adicoes = 0
for i in range(1, len(numeros)):
	divisores1 = divis(numeros[i])
	divisores2 = divis(numeros[i - 1])
	resut = divisores1.intersection(divisores2)
	if resut != {1}:
		new_numeros.append('1')
		adicoes += 1
	new_numeros.append(str(numeros[i]))
print(adicoes)
print(' '.join(new_numeros))


from math import gcd
n = int(input())
ans = []
for c in map(int, input().split()):
	if ans == []:
		ans += [c]
	elif gcd(ans[-1], c) != 1:
		ans += [1, c]
	else:
		ans += [c]
print(len(ans) - n)
print(' '.join(map(str, ans)))


def main():
	from math import gcd
	(n, a, l) = (int(input()), 1, [])
	for b in map(int, input().split()):
		if gcd(a, b) > 1:
			l.append(1)
		l.append(b)
		a = b
	print(len(l) - n)
	print(*l)
main()


n = int(input())
import math
l = input().split()
result = []
count = 0
for i in range(len(l) - 1):
	result.append(l[i])
	if math.gcd(int(l[i]), int(l[i + 1])) != 1:
		result.append(1)
		count += 1
result.append(l[-1])
print(count)
for i in result:
	print(i, end=' ')


from math import sqrt
n = int(input())
a = [int(i) for i in input().split()]
insert = [0] * n
ans = []
cnt = 0

def is_co_prime(A, B):
	t = A % B
	if t == 0:
		return (B == 1, B)
	while True:
		(A, B) = (B, t)
		if A % B:
			t = A % B
		else:
			C = B
			break
	return (C == 1, C)
for i in range(n - 1):
	check = is_co_prime(a[i], a[i + 1])
	if check[0]:
		continue
	else:
		T = int(sqrt(check[1]))
		while True:
			if is_co_prime(a[i], T)[0] and is_co_prime(T, a[i + 1])[0]:
				break
			T += 1
		insert[i] = T
		cnt += 1
for i in range(n):
	ans.append(a[i])
	if insert[i]:
		ans.append(insert[i])
print(cnt)
print(' '.join(map(str, ans)))


from fractions import gcd
n = int(input())
l = list(map(int, input().split()))
ans = []
ctr = 0
i = 0
for i in range(n - 1):
	ans = ans + [l[i]]
	if gcd(l[i], l[i + 1]) != 1:
		ans = ans + [1]
		ctr += 1
ans += [l[-1]]
print(ctr)
print(*ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def gcd(m, n):
	while min(m, n) > 1:
		if m > n:
			m -= n * (m // n)
		elif n > m:
			n -= m * (n // m)
		else:
			return m
	if min(m, n) == 1:
		return 1
	else:
		return max(m, n)
tests = inp()
arr = inlt()
map(int, arr)
i = 0
while i < len(arr) - 1:
	if gcd(arr[i], arr[i + 1]) > 1:
		arr.insert(i + 1, 1)
		i += 2
	else:
		i += 1
print(len(arr) - tests)
string = ''
for elem in arr:
	string = string + str(elem) + ' '
string = string[:len(string) - 1]
print(string)


n = int(input())
array = list(map(int, input().split()))
qnt = 0

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
contador = 0
while contador != len(array) - 1:
	if gcd(array[contador], array[contador + 1]) != 1:
		qnt += 1
		array.insert(contador + 1, 1)
	contador += 1
string = ''
for i in range(len(array)):
	string += str(array[i]) + ' '
print(qnt)
print(string[:len(string) - 1])


import math
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
c = 0
i = 1
while i < n:
	if math.gcd(a[i], a[i - 1]) == 1:
		b.append(a[i])
	else:
		c += 1
		if math.gcd(2, a[i - 1]) == 1 and math.gcd(2, a[i]) == 1:
			b.append(2)
			b.append(a[i])
		elif math.gcd(3, a[i - 1]) == 1 and math.gcd(3, a[i]) == 1:
			b.append(3)
			b.append(a[i])
		else:
			b.append(1)
			b.append(a[i])
	i += 1
print(c)
for i in b:
	print(i, end=' ')
print('')


from math import *
a = int(input())
b = []
s = 0
for i in map(int, input().split()):
	b += [i] + [0]
for i in range(0, 2 * a - 2, 2):
	if gcd(b[i], b[i + 2]) != 1:
		b[i + 1] = 1000003
		s += 1
print(s)
for i in b:
	if i:
		print(i, end=' ')


input()

def nod(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def main():
	a = list(map(int, input().split()))
	out = []
	k = 0
	for i in range(0, len(a) - 1):
		out.append(a[i])
		if nod(a[i], a[i + 1]) != 1:
			out.append(1)
			k += 1
	out.append(a[len(a) - 1])
	str_out = ' '.join(map(str, out))
	print(k)
	print(str_out)
main()


def gcd(a, b):
	while b > 0:
		(a, b) = (b, a % b)
	return a
n = int(input())
A = list(map(int, input().split()))
B = [A[0]]
k = 0
for i in range(n - 1):
	a = A[i]
	b = A[i + 1]
	if gcd(a, b) != 1:
		k += 1
		B.append(1)
	B.append(b)
print(k)
print(*B)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
n = int(input())
a = list(map(int, input().split(' ')))
aa = [a[0]]
for i in range(1, n):
	if gcd(aa[-1], a[i]) > 1:
		aa.append(1)
	aa.append(a[i])
print(len(aa) - n)
print(' '.join(map(str, aa)))


import fractions
import sys
n = int(input())
l = list(map(int, input().split()))
ans = []
for i in range(1, n):
	ans.append(l[i - 1])
	if fractions.gcd(l[i], l[i - 1]) > 1:
		ans.append('1')
ans.append(l[n - 1])
print(len(ans) - n)
for i in ans:
	sys.stdout.write(str(i) + ' ')


from math import gcd
n = int(input())
k = 0
l = list(map(int, input().split()))
p = []
for i in range(n - 1):
	if gcd(l[i], l[i + 1]) > 1:
		p.append(l[i])
		p.append(1)
		k = k + 1
	else:
		p.append(l[i])
p.append(l[-1])
print(k)
print(*p, sep=' ')


def gcd(x, y):
	if y == 0:
		return x
	return gcd(y, x % y)
n = int(input())
a = list(map(int, input().split()))
last = 1
ans = []
for i in range(n):
	if gcd(a[i], last) != 1:
		ans.append(1)
	ans.append(a[i])
	last = a[i]
print(len(ans) - n)
for i in range(len(ans) - 1):
	print(ans[i], end=' ')
print(ans[len(ans) - 1])


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
A = [int(x) for x in input().split()]
B = [A[0]]
for i in range(1, len(A)):
	if gcd(B[-1], A[i]) == 1:
		B += [A[i]]
	else:
		B += [1, A[i]]
print(len(B) - len(A))
print(' '.join(map(str, B)))


def gcd(x, y):
	while y != 0:
		(x, y) = (y, x % y)
	return x
input()
a = list(map(int, input().split()))
total = 0
ans = [a[0]]
for i in range(1, len(a)):
	if gcd(a[i], a[i - 1]) != 1:
		ans.append(1)
		total += 1
	ans.append(a[i])
print(total)
print(' '.join(map(str, ans)))


import sys
import math
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
ara = inara()
ans = []
for i in range(n - 1):
	ans.append(ara[i])
	if math.gcd(ara[i], ara[i + 1]) > 1:
		ans.append(1)
ans.append(ara[n - 1])
print(len(ans) - n)
print(*ans)


import math
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(0, n - 1):
	b += [a[i]]
	if math.gcd(a[i], a[i + 1]) - 1:
		b += [1]
b += [a[-1]]
print(len(b) - n)
for i in b:
	print(i, end=' ')


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
a = list(map(int, input().split()))
b = []
b.append(a[0])
s = 0
for i in range(1, len(a)):
	if gcd(a[i], a[i - 1]) != 1:
		b.append(1)
		s += 1
	b.append(a[i])
print(s)
print(*b)


n = int(input())
a = list(map(int, input().split()))
b = []

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x + y
for i in range(0, n):
	b.append(a[i])
	if i + 1 < n and gcd(a[i], a[i + 1]) != 1:
		b.append(1)
print(len(b) - n)
for x in b:
	print(x, end=' ')


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def coprime(a, b):
	if gcd(a, b) == 1:
		return True
	else:
		return False
n = int(input())
a = list(map(int, input().split()))
ans = []
cnt = 0
for i in range(n - 1):
	if not coprime(a[i], a[i + 1]):
		ans.append(i + 1)
		cnt += 1
cnt2 = 0
for x in ans:
	a.insert(x + cnt2, 1)
	cnt2 += 1
print(cnt)
print(*a)


import fractions
n = int(input())
a = list(map(int, input().split()))
cnt = 0
ans = a[:1]
for i in range(1, len(a)):
	if 1 < fractions.gcd(ans[-1], a[i]):
		for j in range(2, 1000):
			if fractions.gcd(ans[-1], j) == fractions.gcd(a[i], j) == 1:
				cnt += 1
				ans.append(j)
				break
	ans.append(a[i])
print(cnt)
print(' '.join(map(str, ans)))


import sys
import math
n = int(input())
a = list(map(int, input().split()))
i = 1
ans = [a[0]]
while i < n:
	if math.gcd(ans[-1], a[i]) == 1:
		ans.append(a[i])
		i += 1
	else:
		ans.append(1)
print(len(ans) - n)
print(*ans)


import math
n = int(input())
a = list(map(int, input().split()))
ans = ''
res = 0
for i in range(1, n):
	if math.gcd(a[i], a[i - 1]) != 1:
		ans += str(a[i - 1]) + ' '
		ans += '1 '
		res += 1
	else:
		ans += str(a[i - 1]) + ' '
ans += str(a[n - 1]) + ' '
print(res)
print(ans)


import fractions

def coprimeArray(arr, n):
	c = 0
	for i in range(1, n):
		if fractions.gcd(arr[i], arr[i - 1]) != 1:
			c = c + 1
	print(c)
	print(arr[0], end=' ')
	for i in range(1, n):
		if fractions.gcd(arr[i], arr[i - 1]) != 1:
			print(1, end=' ')
		print(arr[i], end=' ')
n = int(input())
arr = list(map(int, input().split()))
coprimeArray(arr, n)
print()


import math

class CodeforcesTask660ASolution:

	def __init__(self):
		self.result = ''
		self.n = 0
		self.array = []

	def read_input(self):
		self.n = int(input())
		self.array = [int(x) for x in input().split(' ')]

	def process_task(self):
		coprimism = [1 if math.gcd(self.array[x - 1], self.array[x]) == 1.0 else 0 for x in range(1, self.n)]
		k = self.n - sum(coprimism) - 1
		new_array = [self.array[0]]
		for x in range(1, self.n):
			if not coprimism[x - 1]:
				new_array.append(1)
			new_array.append(self.array[x])
		self.result = '{0}\n{1}'.format(k, ' '.join([str(x) for x in new_array]))

	def get_result(self):
		return self.result
Solution = CodeforcesTask660ASolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


n = int(input())
a = list(map(int, input().split()))

def getGcd(a, b):
	while True:
		if a < b:
			num = b % a
			b = num
		else:
			num = a % b
			a = num
		if a == 0:
			return b
		elif b == 0:
			return a
(i, count) = (0, 0)
while True:
	if i + 1 > len(a) - 1:
		break
	(num, prox) = (a[i], a[i + 1])
	gcd = getGcd(num, prox)
	if gcd != 1:
		a.insert(i + 1, 1)
		i += 2
		count += 1
	else:
		i += 1
print(count)
print(*a)


from math import gcd
n = int(input())
arr = list(map(int, input().split(' ')))
count = 0
ans = []
for i in range(len(arr) - 1):
	ans += [arr[i]]
	if gcd(arr[i], arr[i + 1]) > 1:
		ans += [1]
		count += 1
ans += [arr[-1]]
print(count)
print(*ans)


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
l = list(map(int, input().split()))
i = 1
while i < len(l):
	if gcd(l[i - 1], l[i]) != 1:
		l = l[:i] + [1] + l[i:]
		i += 2
	else:
		i += 1
print(len(l) - n)
print(*l)


from math import gcd
(n, a) = (int(input()), [*map(int, input().split())])
b = []
b.append(a[0])
cnt = 0
for i in range(1, n):
	if gcd(a[i - 1], a[i]) != 1:
		b.append(1)
		cnt += 1
	b.append(a[i])
print(cnt)
print(*b)


from math import gcd

def SieveOfEratosthenes(n):
	arr = []
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	prime[0] = False
	prime[1] = False
	for p in range(n + 1):
		if prime[p]:
			arr.append(p)
	return arr
n = int(input())
arr = list(map(int, input().split()))
prime = SieveOfEratosthenes(10 ** 5)
ans = []
count = 0
for i in range(n - 1):
	temp = gcd(arr[i], arr[i + 1])
	if temp == 1:
		ans.append(arr[i])
	else:
		ans.append(arr[i])
		count += 1
		for p in prime:
			if arr[i] % p != 0 and arr[i + 1] % p != 0:
				ans.append(p)
				break
ans.append(arr[-1])
print(count)
for i in ans:
	print(i, end=' ')
print()


n = int(input())
num = list(map(int, input().split()))
x = 0
banyak = 0

def gcd(a, b):
	while b != 0:
		(a, b) = (b, a % b)
	return a

def coprime(a, b):
	return gcd(a, b) == 1
while x < len(num) - 1:
	if not coprime(num[x], num[x + 1]):
		p = max(num[x], num[x + 1]) - 1
		q = min(num[x], num[x + 1]) + 1
		banyak += 1
		x += 1
		num.insert(x, 1)
	x += 1
print(banyak)
print(' '.join(list(map(str, num))))


from fractions import gcd
(n, a, v) = (int(input()), list(map(int, input().split())), [])
for (i, ai) in enumerate(a):
	v.append(ai)
	if i < n - 1 and gcd(ai, a[i + 1]) > 1:
		v.append(1)
print(len(v) - len(a))
print(' '.join(map(str, v)))


import math
n = int(input())
ls = list(map(int, input().split()))
result = []
k = 0
for i in range(n - 1):
	if math.gcd(ls[i], ls[i + 1]) == 1:
		result.append(ls[i])
	else:
		result.append(ls[i])
		result.append(1)
		k += 1
result.append(ls[-1])
print(k)
for r in result:
	print(r, end=' ')


n = int(input())
lst = list(map(int, input().strip().split(' ')))
c = 0
l = [lst[0]]
for i in range(1, n):
	if (l[-1] == lst[i] or l[-1] % lst[i] == 0 or lst[i] % l[-1] == 0) and (l[-1] != 1 and lst[i] != 1):
		l.append(1)
		l.append(lst[i])
		c += 1
	elif l[-1] == 1 or lst[i] == 1:
		l.append(lst[i])
	else:
		out = 0
		ins = 0
		if l[-1] > lst[i]:
			ins = l[-1]
			out = lst[i]
		else:
			ins = lst[i]
			out = l[-1]
		while True:
			if ins % out == 0:
				break
			else:
				k = ins // out
				p1 = ins
				ins = out
				out = p1 - out * k
		if out == 1:
			l.append(lst[i])
		else:
			l.append(1)
			l.append(lst[i])
			c += 1
print(c)
for j in range(len(l)):
	print(l[j], end=' ')


import sys
from math import gcd
n = int(input())
a = list(map(int, input().split()))
ans = [a[0]]
for i in range(1, n):
	if gcd(a[i - 1], a[i]) != 1:
		for j in range(2, 10 ** 9):
			if gcd(a[i - 1], j) == 1 and gcd(a[i], j) == 1:
				ans.append(j)
				break
	ans.append(a[i])
print(len(ans) - n)
print(*ans)


import math
n = int(input())
l = []
cnt = 0
l = [int(x) for x in input().split()]
i = 1
while i != len(l):
	if math.gcd(l[i], l[i - 1]) > 1:
		cnt += 1
		l.insert(i, 1)
	i += 1
print(cnt)
for i in l:
	print(i, end=' ')


import math

def printArr(arr):
	for i in arr:
		print(i, end=' ')

def proA(arr):
	ans = []
	i = 0
	c = 0
	while i < len(arr):
		if i == len(arr) - 1:
			ans.append(arr[-1])
			break
		if math.gcd(arr[i], arr[i + 1]) != 1:
			c += 1
			ans.append(arr[i])
			ans.append(1)
		else:
			ans.append(arr[i])
		i += 1
	print(c)
	printArr(ans)
n = int(input())
arr = list(map(int, input().split()))
proA(arr)


import math
n = input()
numbers = list(map(int, input().split()))
i = 0
out = []
last_insert = 0
while i < len(numbers) - 1:
	if math.gcd(numbers[i], numbers[i + 1]) == 1:
		if str(numbers[i]) != last_insert:
			out.append(str(numbers[i]))
		last_insert = str(numbers[i + 1])
		out.append(last_insert)
	else:
		if str(numbers[i]) != last_insert:
			out.append(str(numbers[i]))
		out.append('1')
		last_insert = str(numbers[i + 1])
		out.append(last_insert)
	i += 1
added = len(out) - len(numbers)
if out == []:
	out = [str(i) for i in numbers]
	added = 0
print(added)
print(' '.join(out))


def gcd(x, y):
	if x % y == 0:
		return y
	return gcd(y, x % y)
n = int(input())
arr = list(map(int, input().split()))
ans = str(arr[0])
i = 0
cont = 0
while i < len(arr) - 1:
	mdc = gcd(arr[i], arr[i + 1])
	if mdc == 1:
		i += 1
	else:
		arr = arr[:i + 1] + [1] + arr[i + 1:]
		cont += 1
		i += 2
print(cont)
print(' '.join(map(str, arr)))


import sys, os
from io import BytesIO, IOBase
import collections, itertools, bisect, heapq, math, string
from decimal import *
BUFSIZE = 8192
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def main():
	n = int(input())
	a = list(map(int, input().split()))
	ans = [a[0]]
	for i in range(1, n):
		if math.gcd(a[i], a[i - 1]) != 1:
			ans.append(1)
		ans.append(a[i])
	print(len(ans) - len(a))
	print(' '.join([str(x) for x in ans]))
main()


def mdc(a, b):
	if b == 0:
		return a
	else:
		return mdc(b, a % b)
input()
lista = list(map(int, input().split()))
tamanhoIni = len(lista)
i = 0
while i < len(lista) - 1:
	mdcPar = 1
	if lista[i] > lista[i + 1]:
		mdcPar = mdc(lista[i], lista[i + 1])
	else:
		mdcPar = mdc(lista[i + 1], lista[i])
	if mdcPar == 1:
		i += 1
	else:
		lista.insert(i + 1, 1)
		i += 2
print(len(lista) - tamanhoIni)
print(*lista)


import math
n = int(input())
list1 = list(map(int, input().split()))
list2 = list1.copy()
c = 0
for i in range(n - 1):
	x = list1[i]
	y = list1[i + 1]
	jj = 1
	if math.gcd(x, y) > 1:
		list2.insert(i + 1 + c, 1)
		c += 1
print(c)
print(*list2)


from math import gcd
n = int(input())
a = [int(i) for i in input().split()]
ans = [a[0]]
for i in range(n - 1):
	if gcd(a[i], a[i + 1]) != 1:
		ans.append(1)
	ans.append(a[i + 1])
print(len(ans) - len(a))
print(*ans)


from fractions import gcd
a = int(input())
b = list(map(int, input().split()))
count = 0
i = 0
while i < a - 1:
	if gcd(b[i], b[i + 1]) != 1:
		count += 1
		b.insert(i + 1, 1)
		i += 1
		a += 1
	i += 1
print(count)
print(' '.join(map(str, b)))


def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
n = int(input())
lst = list()
lst = input().split(' ')
k = 0
for i in range(n - 1):
	if gcd(int(lst[i]), int(lst[i + 1])) != 1:
		k += 1
print(k)
ans = list()
p = ''
for i in range(0, n - 1):
	p = p + lst[i] + ' '
	if gcd(int(lst[i]), int(lst[i + 1])) != 1:
		p += '1 '
p += lst[n - 1]
print(p)


from fractions import gcd
n = int(input())
l = list(map(int, input().split(' ')))
k = 0
i = 1
while i < n + k:
	if gcd(l[i], l[i - 1]) != 1:
		k += 1
		l = l[:i] + [1] + l[i:]
	i += 1
print(k)
print(*l)


n = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)

def gcd1(a, b):
	if gcd(a, b) == 1:
		return False
	else:
		return True
i = 0
k = 0
while i < n:
	if i < len(a) - 1:
		if gcd1(a[i], a[i + 1]):
			a.insert(i + 1, 1)
			i += 2
			n += 1
			k += 1
		else:
			i += 1
	else:
		i += 1
print(k)
for i in a:
	print(i, end=' ')


from math import gcd
n = int(input())
A = list(map(int, input().split()))
ans = [A[0]]
i = 1
while i < n:
	if gcd(ans[-1], A[i]) == 1:
		ans.append(A[i])
		i += 1
	else:
		ans.append(1)
print(len(ans) - n)
print(*ans)


import math

def prime(n):
	ok = True
	for i in range(2, int(math.sqrt(n))):
		if n % i == 0:
			ok = False
			break
	if ok:
		return True
	else:
		return False

def fact(a, b):
	ans = 1
	for i in range(a, b + 1):
		ans *= i
	return str(ans) - 1

def comb(n, c):
	return fact(n) // (fact(n - c) * c)

def gcd(a, b):
	(a, b) = (max(a, b), min(a, b))
	rem = []
	lst = -1
	while b != 0:
		(a, b) = (b, a % b)
		if b != 0:
			rem.append(b)
	if rem:
		return rem[-1]
	else:
		return a
n = int(input())
nums = list(map(int, input().split()))
chg = []
k = 0
for i in range(n - 1):
	if gcd(nums[i], nums[i + 1]) != 1:
		chg.append(i + 1)
		k += 1
ans = []
cnt = 0
mrk = 0
add = 1
for i in range(len(chg) + n):
	if chg:
		if i == chg[mrk]:
			ans.append('1')
			if mrk < len(chg) - 1:
				mrk += 1
				chg[mrk] += add
				add += 1
		else:
			ans.append(str(nums[cnt]))
			cnt += 1
	else:
		ans.append(str(nums[cnt]))
		cnt += 1
print(k)
print(' '.join(ans))


import math
n = int(input())
a = list(map(int, input().rstrip().split()))
t = 0
ans = [a[0]]
for i in range(1, n):
	x = ans[-1]
	y = a[i]
	g = math.gcd(x, y)
	if g != 1:
		ans += [1, y]
		t += 1
	else:
		ans += [y]
print(t)
print(*ans)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)

def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	co_primes = []
	count = 0
	for i in range(n):
		if 0 < i and gcd(a[i], a[i - 1]) > 1:
			count += 1
			co_primes.append(1)
		co_primes.append(a[i])
	print(count)
	print(*co_primes)
main()


import bisect
from itertools import accumulate
import os
import sys
import math
from decimal import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def SieveOfEratosthenes(n):
	prime = []
	primes = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if primes[p] == True:
			prime.append(p)
			for i in range(p * p, n + 1, p):
				primes[i] = False
		p += 1
	return prime
n = int(input())
a = list(map(int, input().split()))
dic = {}
p = SieveOfEratosthenes(10 ** 5)
ans = []
for i in range(0, len(a) - 1):
	if math.gcd(a[i], a[i + 1]) == 1:
		ans.append(a[i])
	else:
		for j in range(0, len(p)):
			if math.gcd(a[i], p[j]) == 1 and math.gcd(a[i + 1], p[j]) == 1:
				ans.append(a[i])
				ans.append(p[j])
				break
ans.append(a[-1])
print(len(ans) - n)
print(*ans)


N = int(input())
a = list(map(int, input().split()))

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)
ans = []
for i in range(N):
	ans.append(a[i])
	if i < N - 1 and gcd(a[i], a[i + 1]) != 1:
		ans.append(1)
print(len(ans) - N)
print(*ans)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
cnt = 0
ans = ''
for i in range(1, n):
	if gcd(a[i - 1], a[i]) == 1:
		ans += f'{a[i - 1]} '
	else:
		cnt += 1
		ans += f'{a[i - 1]} 1 '
ans += f'{a[-1]}'
print(cnt)
print(ans)


from fractions import gcd
n = int(input())

def lcm(a, b):
	return a * b // gcd(a, b)
a = list(map(int, input().split()))
i = 1
k = 0
while i < len(a):
	if gcd(a[i - 1], a[i]) > 1:
		a[i:i] = [1]
		i += 1
		k += 1
	i += 1
print(k)
for i in a:
	print(i, end=' ')


def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
n = int(input())
l = list(map(int, input().split()))
nl = []
c = 0
for i in range(n - 1):
	nl.append(l[i])
	if gcd(l[i], l[i + 1]) != 1:
		nl.append(1)
		c += 1
nl.append(l[n - 1])
print(c)
for i in range(len(nl)):
	print(nl[i], end=' ')
print()


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def co_prime(prev, this):
	if gcd(prev, this) > 1:
		yield from [1, this]
		return 1
	else:
		yield this
		return 0

def solver(in_numbers):
	prev = 1
	count = 0
	for this in in_numbers:
		count += (yield from co_prime(prev, this))
		prev = this
	return count

def solve(in_numbers):
	count = (yield from solver(in_numbers))
	print(count)

def main():
	in_count = input()
	in_numbers = map(int, input().split())
	print(' '.join(map(str, solve(in_numbers))))
main()


from fractions import gcd
n = int(input())
a = list(map(int, input().split()))
ans = []
counter = 0
lena = len(a)
for i in range(lena):
	if i != lena - 1:
		if gcd(a[i], a[i + 1]) != 1:
			ans.append(a[i])
			ans.append(1)
			counter += 1
		else:
			ans.append(a[i])
	else:
		ans.append(a[i])
ans = list(map(str, ans))
print(counter)
print(' '.join(ans))


import math
for _ in range(1):
	n = int(input())
	a = list(map(int, input().split()))
	k = 0
	l = []
	for i in range(n - 1):
		if math.gcd(a[i], a[i + 1]) != 1:
			k += 1
			l.append(i + 1)
	l.reverse()
	for i in range(k):
		a.insert(l[i], 1)
	print(k)
	print(*a)


def main():
	n = int(input())
	L = [int(x) for x in input().split()]
	(k, L2) = solver(L)
	print(k)
	for x in L2:
		print(x)

def solver(L):
	primes = primeSieve(10 ** 5)
	L2 = []
	for i in range(len(L) - 1):
		num1 = L[i]
		num2 = L[i + 1]
		divisor = gcd(num1, num2)
		L2.append(num1)
		if divisor != 1:
			for x in primes:
				if num1 % x != 0 and num2 % x != 0:
					L2.append(x)
					break
	L2.append(L[len(L) - 1])
	return (len(L2) - len(L), L2)

def gcd(x, y):
	while x != 0 and y != 0:
		if x >= y:
			x = x % y
		else:
			y = y % x
	return x + y

def primeBools(n):
	result = [True] * n
	result[0] = False
	result[1] = False
	result[2 ** 2:n:2] = [False] * ((n - 2 ** 2 - 1) // 2 + 1)
	for x in range(3, int(n ** 0.5) + 1, 2):
		if result[x] == True:
			result[x ** 2:n:x] = [False] * ((n - x ** 2 - 1) // x + 1)
	return result

def primeSieve(n):
	bools = primeBools(n)
	primes = [i for i in range(len(bools)) if bools[i]]
	return primes
main()


n = int(input())
a = list(map(int, input().split()))

def gcd(x, y):
	if x < y:
		(x, y) = (y, x)
	if y == 0:
		return x
	return gcd(y, x % y)
res = []
cnt = 0
for i in range(1, len(a)):
	x = a[i - 1]
	y = a[i]
	g = gcd(x, y)
	res.append(x)
	if g != 1:
		res.append(1)
		cnt += 1
res.append(a[len(a) - 1])
print(cnt)
print(' '.join(map(str, res)))


from math import gcd

def get_int():
	from sys import stdin
	return int(stdin.readline().replace('\n', ''))

def get_int_list():
	from sys import stdin
	return [int(x) for x in stdin.readline().replace('\n', '').split(' ')]

def get_str():
	from sys import stdin
	return stdin.readline().replace('\n', '')

def _print(_list):
	from sys import stdout
	for e in _list:
		stdout.write(str(e) + ' ')
	print()

def LCM(a, b):
	return a * b // gcd(a, b)

def are_coprimes(a, b):
	return gcd(a, b) == 1

def insert_not_coprime(_list, index):
	return _list[0:index + 1] + [1] + _list[index + 1:len(_list)]

def coprime(_list):
	(n, i) = (0, 0)
	while i < len(_list) - 1:
		if not are_coprimes(_list[i], _list[i + 1]):
			_list = insert_not_coprime(_list, i)
			n += 1
			i += 1
		i += 1
	return (_list, n)
n = get_int()
arr = get_int_list()
(arr, n) = coprime(arr)
print(n)
_print(arr)