题目描述

少女漫画与情歌中的语言……总是闪闪发光。我不需要词典就能明白它们的含义……但我自己却从未亲身感受过。

——小糸侑

侑正在尝试加入学生会！不幸的是，她被要求去做文书工作……灯子要她填写各种学生会文件中的空白。

给你一个部分填充的非负整数数组 $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$ 的方案中，求出 $|b_1 + b_2 + \dots + b_{n-1}|$ 的最小值。

此外，输出能够达到这个最小值的数组。如果有多种这样的数组，请输出字典序最小的那一个 $^{\text{∗}}$。

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

输入格式

第一行包含一个整数 $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$。

输出格式

对于每个测试用例，第一行输出最小可能的 $|b_1 + b_2 + \dots + b_{n-1}|$。第二行输出 $n$ 个整数，表示达到最小值的 $a_1, a_2, \dots, a_n$（字典序最小的那组）。

样例

6
4
2 -1 7 1
4
-1 2 4 -1
8
2 -1 1 5 11 12 1 -1
3
-1 -1 -1
3
2 5 4
2
-1 5

1
2 0 7 1
0
0 2 4 0
0
2 0 1 5 11 12 1 2
0
0 0 0
2
2 5 4
0
5 5

样例说明

在第一个样例中，我们将数组填成 $a = [2, 0, 7, 1]$，其差分数组为 $b = [-2, 7, -6]$。

$b$ 所有元素之和的绝对值为 $1$。可以证明这是最小可能值。同时可以证明这是字典序最小的 $a$。

由 ChatGPT 5 翻译

来源

Codeforces 2171B，英文题名 Yuu Koito and Minimum Absolute Sum。