Memory Fragments Reassembly

Alice has a sequence of memory fragments, each represented by a non‐negative integer. The fragments must be arranged in the given order. Two adjacent fragments can be joined together if and only if the sum of their memories is a perfect square (i.e. there exists an integer \(k\ge0\) such that the sum equals \(k^2\)).

To help piece together her memories, Alice is allowed to polish (modify) some of the fragments. In one operation, she can choose any fragment and change its memory to any non‐negative integer. Note that once a fragment is not modified its value remains unchanged. Your task is to determine the minimum number of operations needed so that after the modifications, for every adjacent pair \(b_i\) and \(b_{i+1}\), the sum \(b_i+b_{i+1}\) is a perfect square. You must also output one valid final sequence.

Formal Statement:

Given an array of non‐negative integers \(a_1,a_2,\dots,a_n\), you are allowed to perform the following operation any number of times: choose an index \(i\) (\(1\le i\le n\)) and set \(a_i\) to any non‐negative integer \(x\). Determine the minimum number of operations required so that there exists an array \(b_1,b_2,\dots,b_n\) satisfying:

[ \forall; 1\le i<n,\quad b_i+b_{i+1}=k^2 \quad \text{for some integer}; k\ge0, ]

and for every index that is not modified we have \(b_i=a_i\). If a fragment is modified, you are free to choose its new value, but the final sequence must satisfy the adjacent sum condition.

Note: A number \(y\) is a perfect square if there exists an integer \(k \ge 0\) with \(y=k^2\). In particular, \(0\) is a perfect square (\(0^2 = 0\)).

inputFormat

The input consists of two lines. The first line contains a single integer \(n\) (\(1\le n \le 10^5\)), representing the number of fragments. The second line contains \(n\) non‐negative integers \(a_1,a_2,\dots,a_n\), separated by spaces.

outputFormat

Output two lines. The first line contains a single integer representing the minimum number of modifications required. The second line contains \(n\) non‐negative integers \(b_1,b_2,\dots,b_n\) separated by spaces, which is one valid final sequence satisfying \(b_i+b_{i+1}\) is a perfect square for all \(1\le i<n\).

sample

3
1 3 6

0
1 3 6