Yuu Koito and Minimum Absolute Sum

The key thing is that the scary-looking expression is a total scam.

We are asked to minimize

$$|b_1+b_2+\dots+b_{n-1}|,$$

where

$$b_i=a_{i+1}-a_i.$$

Now expand the sum:

$$(a_2-a_1)+(a_3-a_2)+\dots+(a_n-a_{n-1}).$$

Everything in the middle cancels. We get

$$b_1+b_2+\dots+b_{n-1}=a_n-a_1.$$

So the whole problem is just:

$$\text{minimize } |a_n-a_1|.$$

The middle elements have absolutely no effect on the value. They only matter for lexicographic smallest output.

Endpoint Cases

Only $a_1$ and $a_n$ affect the minimum.

If both are fixed, then the answer is forced:

$$|a_n-a_1|.$$

No choice can change it.

If exactly one endpoint is blank, set it equal to the fixed endpoint. Then

$$|a_n-a_1|=0,$$

which is obviously the best possible value.

If both endpoints are blank, set both equal. The minimum is again $0$. For lexicographic smallest order, choose the smallest nonnegative value for $a_1$, which is $0$. Then $a_n$ must also be $0$.

What About The Middle?

After the endpoints are handled, every blank middle element should be $0$.

Why? Because middle elements do not affect the objective, and lexicographic order rewards smaller earlier values. Since values must be nonnegative, $0$ is always best. No fancy DP, no hidden trap, no quadratic nonsense. Just fill the dead weight with zeroes.

Algorithm

1. Read the array.
2. Decide the endpoint values:
   • If $a_1=-1$ and $a_n=-1$, set both to $0$.
   • If $a_1=-1$, set $a_1=a_n$.
   • If $a_n=-1$, set $a_n=a_1$.
3. Replace every remaining $-1$ with $0$.
4. Output $|a_n-a_1|$ and the array.

Correctness Proof

Let the final filled array be $a$.

By telescoping,

$$\sum_{i=1}^{n-1} b_i =\sum_{i=1}^{n-1}(a_{i+1}-a_i) =a_n-a_1.$$

Therefore the objective value is exactly $|a_n-a_1|$, and no interior element can affect it.

If both endpoints are fixed, every valid filled array has the same endpoint values, so the minimum is forced.

If at least one endpoint is blank, we can make the two endpoints equal by assigning the blank endpoint appropriately. Since absolute values are always nonnegative, achieving $0$ is optimal.

Among all optimal arrays, the construction chooses the smallest possible value at the first endpoint whenever it is free. Then, for every remaining blank interior position, it chooses $0$, the smallest allowed value. These positions do not affect optimality, so choosing $0$ greedily at each such position gives the lexicographically smallest optimal array.

Thus the algorithm outputs both the minimum possible value and the lexicographically smallest array achieving it.

Complexity

Each test case is processed in $O(n)$ time and uses $O(n)$ memory for the array. Across all test cases, this is $O(\sum n)$, which easily fits.