题目描述

记忆的碎片散落在各个角落，而爱丽丝想把它们拼合在一起。

碎片的顺序是给定的，因为记忆显然不能反过来进行。但是，碎片各自的形状和内容是可以打磨和修正的——毕竟所有人的记忆都会歪曲和遗忘。

每个碎片上的记忆都可以用一个非负整数来表示。而相邻的两个碎片能够完整地拼合起来，当且仅当它们记忆的和是一个完全平方数。

现在，爱丽丝可以打磨若干块碎片，使得每一对相邻的碎片都能够完整地拼合起来。对于每一次打磨，爱丽丝可以选择一块碎片，将这块碎片上的记忆修改为任意一个非负整数。爱丽丝想知道，她至少要打磨多少块碎片，才能实现她的目标。同时，她还希望你给出打磨之后，每块碎片上留有的记忆是多少。

形式化题面

给定一个非负整数序列 $\{a_n\}$，我们定义一次操作是任意选择一个 $i\in [1,n]$ 并将 $a_i$ 改为任意一个非负整数 $x$。

问至少进行几次操作才可以满足 $\forall i\in [1,n-1]$ 有 $a_i+a_{i+1}$ 为完全平方数，并给出修改方案。

输入格式

第一行输入一个整数 $n$，表示记忆碎片的个数。

第二行输入一个长度为 $n$ 的非负整数序列 $a$，表示每个记忆碎片上的记忆。

输出格式

第一行输出一个整数，表示最少打磨次数。

第二行输出一个长度为 $n$ 的整数序列，表示所有打磨过后的记忆碎片上的记忆。

你必须保证你打磨后的记忆满足题目条件，且与你给出的最少打磨次数相符，并满足每个碎片上的记忆都在 $[0,10^{18}]$ 的范围内。

4
1 3 5 8

1
1 3 1 8

3
3 4 5

1
0 4 5

提示

样例解释

对于第一组样例，不难证明爱丽丝至少要打磨一块碎片才能使所有的记忆满足条件。

请一定注意记忆碎片的顺序是不能改变的。

评分规则

如果你对于某一测试点输出的最少打磨次数是正确的，你将获得该测试点 $30\%$ 的分数。

如果你在最少打磨次数正确的基础上给出了正确的构造，你将获得该测试点 $100\%$ 的分数。

如果你只会求解最少打磨次数，那也请你在第二行输出以空格隔开的 $n$ 个在 $[0,10^{18}]$ 范围内的整数，否则可能被判为 $0$ 分。

请注意，你在每个 subtask 中得到的 $30\%$ 分数会被下取整计算。

数据范围

本题采用捆绑测试。

$\text{Subtask}$	$n\le$	$a_i\le$	特殊性质	分值
$1$	$2$	$10^8$		$5$
$2$	$3$			$20$
$3$	$4$			$15$
$4$	$10^3$
$5$	$10^6$	$10^4$		$10$
$6$		$10^8$	$\text{A}$
$7$				$25$

特殊性质 $\text{A}$：$\forall 1\le i,j\le n$ 满足 $a_i=a_j$。

对于 $100\%$ 的数据满足 $1\le n\le 10^6$，$0\le a_i\le 10^8$。