小 \(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 。

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

Subtask ID	附加限制	分数
1	\(n \le 10\)	5
2	\(n \le 20\)	10
3	\(n \le 10^3\)	15
4	\(n \le 10^5\)	10
5	\(n \in [10^5,10^5+100]\)	15
6	\(n \in [1.5 \times 10^5,1.5 \times 10^5+100]\)	15
7	\(n \le 3\times 10^5\)	5
8	\(n \le 10^6\)	25

下发文件

a_little_cut Round 2 下发文件