Make it Zero

The bound of 17 is doing a little stage magic here: the real answer is only $-1$, $1$, or $2$.

What a valid operation implies

Suppose an operation uses array $b$ and split point $k$. Then

$$\sum_{i=1}^{k} b_i = \sum_{i=k+1}^{n} b_i = r.$$

So this operation removes total $2r$, always even.

Also, for any fixed position $j$, the removed amount $b_j$ lies on one side of the split, whose total is $r$. Therefore $b_j \le r$, which means $b_j$ is at most half of this operation's removed total.

Now sum that inequality over all operations. If the initial total is $S$, position $j$ removes exactly $a_j$ overall, while all operations together remove $S$ overall. So we must have

$$S \text{ is even}, \qquad a_j \le \frac{S}{2} \text{ for every } j.$$

If either condition fails, print $-1$. This is not just a vibe check; it is forced.

When one operation is enough

If we finish in one operation, then the selected array must be $b=a$, because every element has to be fully subtracted immediately. That is valid exactly when there is some split point with prefix sum $S/2$.

So after computing prefix sums:

• if a prefix equals $S/2$, output 1 and the original array;
• otherwise, if the array is still possible, we will build exactly two operations.

The two-operation construction

Let $H=S/2$. Since no prefix equals $H$, find the first index $p$ such that the prefix sum through $p$ is greater than $H$.

Write the array as three parts:

• left block before $p$, with sum $x$;
• pivot $a_p=y$;
• right block after $p$, with sum $z$.

By definition of $p$,

$$x < H < x+y.$$

Set

$$d = H-x.$$

So $d>0$, and because $x+y>H$, we have $d<y$, meaning the pivot has enough value to contribute $d$ to the second operation.

We also need the right side to contribute total $d$. This is where the max-element condition matters. Since $y \le H$,

$$z = 2H-x-y \ge 2H-x-H = H-x = d.$$

So the right suffix has enough total value. Choose any amounts $c_i$ from positions after $p$ with $0 \le c_i \le a_i$ and $\sum c_i=d$. Greedily taking from the end is fine.

Now define the second operation:

• $b^{(2)}_p=d$;
• $b^{(2)}_i=c_i$ for $i>p$;
• $b^{(2)}_i=0$ for $i<p$.

This operation is valid by splitting right after $p$: the prefix side has sum $d$, and the suffix side also has sum $d$.

Define the first operation as everything not used in the second operation:

$$b^{(1)}_i = a_i - b^{(2)}_i.$$

Check its split right before $p$. The left side has sum $x$. The right side has

$$(y-d)+(z-d)=y+z-2d=(2H-x)-2(H-x)=x.$$

So the first operation is valid too.

After the first operation, the remaining array is exactly $b^{(2)}$, and the second operation deletes it. Done.

Why this is minimum

• If the impossible conditions fail, answer is $-1$.
• Else, if a prefix sum is $S/2$, answer is $1$.
• Else, one move is impossible because one move would force $b=a`, which would require such a prefix. The construction gives$2$, so the minimum is$2$.

The algorithm is linear: compute sum/max/prefixes, then maybe greedily carve $d$ from the suffix. Total complexity is $O(n)$ per test case.