该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

Special for beginners, ^_^

Description

给定一个长度为n的序列，你可以在任意位置添加任意大小的正整数，徐老师想知道至少需要添加多少个数字才能保证相邻数字两两互质，请你回答添加数量和字典序最小的构造方案

Format

Input

第一行一个正整数$n(n \leq 10^5)$，表示数组长度

第二行n个元素$a_i(1 \leq a_i \leq 10^9)$，表示数组元素

Output

第一行输出需要添加的数字数量 第二行给出构造方案

Samples

4
6 3 2 8

2
6 1 3 2 1 8

Limitation

1s, 1024KiB for each test case.