悠正在尝试学生会!不幸的是,她被迫做文书工作……灯子要她填写各种学生会文件中的空白。
给定一个部分填充的非负整数数组 $$$a_1, a_2, \dots, a_n$$$,其中空白元素用 $$$-1$$$ 表示。您希望用非负整数填充空白元素,以便最小化其差异数组中元素之和的绝对值。
更正式地,令 $$$b$$$ 为长度 $$$n-1$$$ 的数组,使得对于所有 $$$1\leq i\leq n-1$$$,$$$b_i = a_{i+1} - a_i$$$。找出 $$$|b_1 + b_2 + \dots + b_{n-1}|$$$ 的最小可能值,以所有可能的方式填充 $$$a$$$ 的空白元素。
此外,输出达到该最小值的数组。如果有多个这样的数组,则输出其中一个 字典顺序最小$$$^{\text{*}}$$$。
$$$^{\text{*}}$$$对于长度为$$$n$$$的两个任意数组$$$c$$$和$$$d$$$,我们说$$$c$$$是 按字典顺序较小 比 $$$d$$$ 如果存在索引 $$$i$$$ ($$$1\leq i\leq n$$$) 使得 $$$c_j = d_j$$$ 对于所有 $$$j \lt i$$$ 和 $$$c_i \lt d_i$$$。换句话说,$$$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$$$ 的值在字典顺序最小的数组中达到这个最小值。
示例
输入复制
642 -1 7 14-1 2 4 -182 -1 1 5 11 12 1 -13-1 -1 -132 5 42-1 5
输出复制
12 0 7 100 2 4 002 0 1 5 11 12 1 200 0 022 5 405 5
注意
在第一个示例中,我们填充数组 $$$a = [2, 0, 7, 1]$$$,这会产生差异数组 $$$b = [-2, 7, -6]$$$。
$$$b$$$ 中元素之和的绝对值为$$$1$$$。可以证明这是最小可能的。此外,可以证明这是达到该最小值的字典顺序最小的数组$$$a$$$。