Description

Given an array of length $n$ whose elements are $0$ or $1$.

Now you may choose some (possibly $0$) elements with value $0$ and change them to $1$.

Let:

• $x$ be the length of the longest consecutive subarray of $1$s (by definition, if all numbers are $0$, then $x = 0$);
• $y$ be the number of modified elements.

Find how to modify the array to maximize $x - y$, and construct one valid plan (output the modified array).

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$ indicating the number of test cases.

The next $2 \times T$ lines describe the test cases, where every $2$ lines correspond to one test case.

In each test case, the first line contains an integer $n$, the length of the array.

The second line contains $n$ integers ($0$ or $1$), representing the given array.

Output Format

Output a total of $2 \times T$ lines, where every $2$ lines correspond to one test case.

In each test case, on the first line output an integer, the maximum value of $x - y$.

On the second line output $n$ integers ($0$ or $1$), representing the modified array. If there are multiple solutions, output any one of them.

1
1
1

1
1

2
3
1 0 1
5
0 1 0 1 0

2
1 1 1
2
0 1 1 1 1

Hint

This problem uses bundled tests.

For all testdata, it is guaranteed that $T \le 10$ and $1 \le n \le 10^5$, and the array elements $\in \{0,1\}$.

• Subtask 1 (70 points): $1 \le n \le 10$.
• Subtask 2 (30 points): no additional constraints.

Translated by ChatGPT 5