← 返回题目列表

Codeforces · 660/A

A. 互质数组

中文机器翻译题面 查看原题

给定一个包含 n 个元素的数组,您必须以尽可能少的移动次数将其变成互质数组。

在每次移动中,您可以在数组中的任何位置插入任何不大于 109 的正整数。

如果一个数组的任何两个相邻数字互质,则该数组是互质的。

在数论中,如果唯一能整除两个整数 a 和 b 的正整数是 1,则称这两个整数 a 和 b 互质。

输入

第一行包含整数 n (1 ≤ n ≤ 1000) — 给定数组中的元素数量。

第二行包含 n 个整数 ai (1 ≤ ai ≤ 109) — 数组 a 的元素。

输出

在第一行打印整数 k — 添加到数组 a 使其互质所需的最少元素数。

第二行应包含 n + k 个整数 aj — 向数组 a 添加 k 个元素后的元素。请注意,新数组应该是互质的,因此任何两个相邻的值都应该是互质的。另外,新数组应该从原始数组 a 中添加 k 个元素来获得。

如果有多个答案,您可以打印其中任何一个。

示例

输入 #1

3
2 7 28

输出 #1

1
2 7 9 28