{"raw_statement":[{"iden":"statement","content":"记忆的碎片散落在各个角落，而爱丽丝想把它们拼合在一起。\n\n碎片的顺序是给定的，因为记忆显然不能反过来进行。但是，碎片各自的形状和内容是可以打磨和修正的——毕竟所有人的记忆都会歪曲和遗忘。\n\n每个碎片上的记忆都可以用一个**非负整数**来表示。而相邻的两个碎片能够完整地拼合起来，当且仅当它们记忆的和是一个**完全平方数**。\n\n现在，爱丽丝可以打磨若干块碎片，使得每一对相邻的碎片都能够完整地拼合起来。对于每一次打磨，爱丽丝可以选择一块碎片，将这块碎片上的记忆修改为任意一个**非负整数**。爱丽丝想知道，她至少要打磨多少块碎片，才能实现她的目标。同时，她还希望你给出打磨之后，每块碎片上留有的记忆是多少。\n\n**形式化题面**\n\n给定一个**非负整数**序列 $\\{a_n\\}$，我们定义一次操作是任意选择一个 $i\\in [1,n]$ 并将 $a_i$ 改为任意一个**非负整数** $x$。\n\n问至少进行几次操作才可以满足 $\\forall i\\in [1,n-1]$ 有 $a_i+a_{i+1}$ 为**完全平方数**，并给出修改方案。"},{"iden":"input","content":"第一行输入一个整数 $n$，表示记忆碎片的个数。\n\n第二行输入一个长度为 $n$ 的非负整数序列 $a$，表示每个记忆碎片上的记忆。"},{"iden":"output","content":"第一行输出一个整数，表示最少打磨次数。\n\n第二行输出一个长度为 $n$ 的整数序列，表示所有打磨过后的记忆碎片上的记忆。\n\n你必须保证你打磨后的记忆满足题目条件，且与你给出的最少打磨次数相符，并满足每个碎片上的记忆都在 $[0,10^{18}]$ 的范围内。"},{"iden":"note","content":"**样例解释**\n\n对于第一组样例，不难证明爱丽丝至少要打磨一块碎片才能使所有的记忆满足条件。\n\n请一定注意记忆碎片的顺序是不能改变的。\n\n**评分规则**\n\n如果你对于某一测试点输出的最少打磨次数是正确的，你将获得该测试点 $30\\%$ 的分数。\n\n如果你在最少打磨次数正确的基础上给出了正确的构造，你将获得该测试点 $100\\%$ 的分数。\n\n如果你只会求解最少打磨次数，那也请你在第二行输出以空格隔开的 $n$ 个在 $[0,10^{18}]$ 范围内的整数，否则可能被判为 $0$ 分。\n\n请注意，你在每个 subtask 中得到的 $30\\%$ 分数会被下取整计算。\n\n**数据范围**\n\n**本题采用捆绑测试**。\n\n| $\\text{Subtask}$ | $n\\le$ | $a_i\\le$ | 特殊性质 | 分值 |\n| :----------: | :----------: | :----------: | :----------: | :----------: |\n| $1$ | $2$ | $10^8$ |  | $5$ |\n| $2$ | $3$ | $10^8$ |  | $20$ |\n| $3$ | $4$ | $10^8$ |  | $15$ |\n| $4$ | $10^3$ | $10^8$ |  | $15$ |\n| $5$ | $10^6$ | $10^4$ |  | $10$ |\n| $6$ | $10^6$ | $10^8$ | $\\text{A}$ | $10$ |\n| $7$ | $10^6$ | $10^8$ |  | $25$ |\n\n特殊性质 $\\text{A}$：$\\forall 1\\le i,j\\le n$ 满足 $a_i=a_j$。\n\n对于 $100\\%$ 的数据满足 $1\\le n\\le 10^6$，$0\\le a_i\\le 10^8$。"}],"translated_statement":null,"sample_group":[["4\n1 3 5 8","1\n1 3 1 8"],["3\n3 4 5","1\n0 4 5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}