B. Юу Които и минимальная абсолютная сумма
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Юу пробует себя в студенческом совете! К сожалению, её заставляют заниматься канцелярской работой... Токо хочет, чтобы она заполнила пробелы в различных документах студенческого совета.

Вам дан частично заполненный массив неотрицательных целых чисел $$$a_1, a_2, \dots, a_n$$$, где пропущенные элементы обозначены как $$$-1$$$. Вы хотите заполнить пропуски неотрицательными целыми числами так, чтобы минимизировать абсолютное значение суммы элементов в его массиве разностей.

Более формально, пусть $$$b$$$ — это массив длины $$$n-1$$$, такой что $$$b_i = a_{i+1} - a_i$$$ для всех $$$1\leq i\leq n-1$$$. Найдите минимально возможное значение $$$|b_1 + b_2 + \dots + b_{n-1}|$$$ среди всех возможных способов заполнения пропущенных элементов массива $$$a$$$.

Кроме того, выведите массив, который достигает этого минимума. Если таких массивов несколько, выведите тот, который является лексикографически наименьшим$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$Для двух произвольных массивов $$$c$$$ и $$$d$$$ длины $$$n$$$ мы говорим, что $$$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$$$ в лексикографически наименьшем массиве, достигающем этого минимума.

Пример
Входные данные
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$$$, который достигает этого минимума.