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

小 $R$ 喜欢玩 Florr.io 。他有 $n$ 个花瓣槽位，每个槽位上的花瓣种类为 $a_i$ ，需要满足 $1 \le a_i \le 3 \times 10^5$ 且 $a_i \in \Z$ 。

为了最大化他的攻击力，小 $R$ 想让他的任意两个相邻槽位上花瓣种类之积互不相等。

在此基础上，小 $E$ 想让小 $R$ 花瓣的种类数尽量少。

形式化的，你需要构造整数序列 $a$ ，使得 $\forall 1 \le i \le n,1 \le a_i \le 3\times 10^5 \\ \forall 1 \le i<j \le n-1,a_{i}a_{i+1} \neq a_j a_{j+1}$ ，并使得 $a$ 序列中的不同元素个数最少。

输入格式

一行一个整数 $n$ 。

输出格式

第一行一个数 $m$ ，表示 $a$ 序列中不同元素的个数。

第二行 $n$ 个数，表示 $a_i$ 。

注意下发的输出文件中不会包含真实的 a 序列输出，只会包含 a 序列中不同元素个数的最小值。

样例输入 1

5

样例输出 1

3
998 244 353 353 998

样例解释

可以验证样例输出合法。

显然还有其他满足条件的输出，选手只需要输出任意一种即可获得分数。

样例输入 2

见下发文件中的 ex_array2.in 。该样例满足子任务 $2$ 的限制。

样例输出 2

见下发文件中的 ex_array2.ans 。该样例满足子任务 $2$ 的限制。

样例输入 3

见下发文件中的 ex_array3.in 。该样例满足子任务 $3$ 的限制。

样例输出 3

见下发文件中的 ex_array3.ans 。该样例满足子任务 $3$ 的限制。

样例输入 4

见下发文件中的 ex_array4.in 。该样例满足子任务 $4$ 的限制。

样例输出 4

见下发文件中的 ex_array4.ans 。该样例满足子任务 $4$ 的限制。

样例输入 5

见下发文件中的 ex_array5.in 。该样例满足子任务 $8$ 的限制。

样例输出 5

见下发文件中的 ex_array5.ans 。该样例满足子任务 $8$ 的限制。

数据范围与提示

本题包含自定义校验器 (spj) 。

本题评分方式如下：

​ 1.如果你输出的 $a_i$ 不满足 $1\le a_i \le 3\times 10^5$，**或你输出的 $m$ 与 $a$ 序列中的不同元素个数不同**，得 $0$ 分；

​ 2.如果你输出的 $a_i$ 不满足 $\forall1\le i<j \le n,a_ia_{i+1}\neq a_ja_{j+1}$ ，但你输出的 $m$ 与真实的最小值相同，你可以获得该测试点 $20\%$ 的分数。若你输出的 $m$ 与真实最小值不同，得 $0$ 分。

​ 3.如果你输出的 $a_i$ 满足上述所有条件，设你的构造中 $a_i$ 的不同元素个数为 $A$ , $a_i$ 中不同元素个数的最小值为 $B$ ，则你可以获得该测试点 $x \%$ 的分数。

​ 若 $A > 2B$ ，$x = 20$ ；若 $B+1 < A \le 2B$ ，$x=40$ ；若 $A=B+1$ ，$x=60$ ；若 $A=B$ ，$x=100$ 。

我们在下发文件中下放了本题的 checker，用于检测你构造方案的合法性。

注意下发的输出文件中不会包含真实的 a 序列输出，只会包含 a 序列中不同元素个数的最小值。

Checker 的使用方式：在对应目录下打开终端，输入命令 checker [input] [output] [answer] 。

其中 input 表示输入文件名称，output 表示你的输出文件名称，answer 表示答案文件名称。

一个可能的命令为 checker ex_array1.in array.out ex_array1.ans 。

本题为子任务评测，每个子任务的得分为其中所有测试点得分的 最小值 。

下发文件

a_little_cut Round 2 下发文件