CF2171B.Yuu Koito and Minimum Absolute Sum

The words in shoujo manga and love songs... they're always sparkling brightly. I don't need a dictionary to understand the meaning... but I've never felt them for myself.

— Yuu Koito

Yuu is trying out the student council! Unfortunately, she is being forced to do clerical work... Touko wants her to fill out the blanks in various student council documents.

You are given a partially filled array of nonnegative integers $a_1, a_2, \dots, a_n$, where blank elements are denoted with $-1$. You would like to fill in the blank elements with nonnegative integers, such that the absolute value of the sum of the elements in its difference array is minimized.

More formally, let $b$ be the array of length $n-1$ such that $b_i = a_{i+1} - a_i$ for all $1\leq i\leq n-1$. Find the minimum possible value of $|b_1 + b_2 + \dots + b_{n-1}|$, across all possible ways to fill in the blank elements of $a$.

Additionally, output the array that achieves this minimum. If there are multiple such arrays, output the one that is lexicographically smallest$^{\text{∗}}$.

$^{\text{∗}}$For two arbitrary arrays $c$ and $d$ of length $n$, we say that $c$ is lexicographically smaller than $d$ if there exists an index $i$ ($1\leq i\leq n$) such that $c_j = d_j$ for all $j \lt i$, and $c_i \lt d_i$. In other words, $c$ and $d$ differ in at least one index, and at the first index at which they differ, $c_i$ is smaller than $d_i$.

少女漫画和情歌中的词语……总是闪耀着耀眼的光芒。我不需要字典就能理解它们的含义……但我却从未真正切身感受过。

——小野夕

夕正在尝试加入学生会！但不幸的是，她被迫做一些文书工作……藤子希望她填写学生会各类文件中的空白处。

给你一个部分填充的非负整数数组 $a_1, a_2, \dots, a_n$，其中空白元素用 $-1$ 表示。你需要将所有空白元素替换为非负整数，使得其差分数组中所有元素之和的绝对值最小。

更准确地说，令 $b$ 为长度为 $n-1$ 的数组，满足对所有 $1\leq i\leq n-1$，有 $b_i = a_{i+1} - a_i$。在所有可能的 $a$ 数组（即所有将 $-1$ 替换为非负整数的方式）中，求 $|b_1 + b_2 + \dots + b_{n-1}|$ 的最小可能值。

此外，请输出达到该最小值的数组 $a$。若存在多个这样的数组，请输出字典序最小的那个$^{\text{∗}}$。

$^{\text{∗}}$对于两个任意长度为 $n$ 的数组 $c$ 和 $d$，我们称 $c$ 的字典序小于 $d$，当且仅当存在某个下标 $i$（$1\leq i\leq n$），使得对所有 $j < i$ 都有 $c_j = d_j$，且 $c_i < d_i$。换言之，$c$ 与 $d$ 至少在一个位置上不同，且在第一个不同的位置 $i$ 上，$c_i$ 小于 $d_i$。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\leq n\leq 2\cdot 10^5$).

The second line of each test case contains $n$ integers, $a_1, a_2, \dots, a_n$ ($-1\leq a_i \leq 10^6$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）—— 表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2\leq n\leq 2\cdot 10^5$）。

每个测试用例的第二行包含 $n$ 个整数：$a_1, a_2, \dots, a_n$（$-1\leq a_i \leq 10^6$）。

保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。

For each test case, on the first line, output the minimum possible value of $|b_1 + b_2 + \dots + b_{n-1}|$. Then, on the second line, output $n$ integers, the values of $a_1, a_2, \dots, a_n$ in the lexicographically smallest array achieving this minimum.

对于每个测试用例，第一行输出 $|b_1 + b_2 + \dots + b_{n-1}|$ 的最小可能值。然后，在第二行输出 $n$ 个整数，即在达到该最小值的所有数组中字典序最小的数组 $a_1, a_2, \dots, a_n$ 的取值。

In the first example, we fill in the array $a = [2, 0, 7, 1]$, which yields the difference array $b = [-2, 7, -6]$.

The absolute value of the sum of the elements in $b$ is $1$. It can be proven that this is the minimum possible. Furthermore, it can be proven that this is the lexicographically smallest array $a$ that achieves this minimum.

在第一个例子中，我们填充数组 $a = [2, 0, 7, 1]$，得到差分数组 $b = [-2, 7, -6]$。

$ b $ 中所有元素之和的绝对值为 $1$。可以证明这是可能的最小值。此外，还可以证明，这是达到该最小值的所有数组 $a$ 中字典序最小的一个。