神殿的平衡序列

题目描述

在远古的「均衡神殿」中，供奉着一条由非负整数组成的序列。祭司们称其为——「平衡序列」。

传说中，若从这条序列中截取任何一段长度至少为 2 的连续符文，那么：

• 位于 原序列偶数位置（下标从 1 开始）的符文力量之和必须 大于等于 位于 原序列奇数位置 的符文力量之和。

只有满足这一律法，序列才能保持神殿的平衡。

然而岁月侵蚀，符文力量紊乱。你作为神殿的修补者，每次只能将某个符文的力量 减少 1（不能减为负）。你的任务是，通过最少的操作次数，使得序列重新成为平衡序列。

形式化的，给定一个长度为 $n$ 的非负整数序列 $a_1, a_2, \ldots, a_n$，如果对于任意的 $1 \leq l < r \leq n$ 且 $r - l + 1 \geq 2$，都有：在区间 $[l,r]$ 内，$\sum_{2\mid i} a_i \geq \sum_{2\nmid i} a_i$，则称序列 $a$ 为 平衡序列。 对于每次操作，你可以选择一个下标 $i$（$1 \leq i \leq n$），并将 $a_i$ 减少 $1$（前提是 $a_i > 0$）。 你需要计算出将序列 $a$ 变为平衡序列所需的最少操作次数，并输出变换后的平衡序列。

输入格式

每组测试数据包含多个测试用例。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。

第二行为 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 10^9$），表示数组 $a$ 的元素。

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

输出格式

对于每个测试用例，第一行输出一个整数，表示把数组 $a$ 变为 平衡序列 所需的最少操作次数。

第二行输出$n$ 个非负整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 10^9$），表示平衡序列 $a_i$ 的元素，如果有多组，则输出任意一组。

样例 1

8
4
3 8 4 4
4
0 2 3 5
2
3 1
5
2 3 1 4 2
4
0 2 4 1
5
3 1 4 5 1
11
3 0 5 4 4 5 3 0 3 4 1
12
410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354 801228787 44181004 1000000000 3829103

0
3 8 4 4
1
0 2 2 5
2
1 1
0
2 3 1 4 2
3
0 2 1 1
6
1 1 0 5 1
14
0 0 0 4 4 5 0 0 0 4 1
4450984776
10753674 10753674 0 193331255 193331255 279719251 86387996 412553354 44181004 44181004 0 3829103

提示

在第一个测试用例中，数组 $a$ 已经是平衡序列，因此答案为 $0$。以下是每个子数组的检查：

在第二个测试用例中，数组 $a$ 不是平衡序列：

但是，如果我们对下标 $3$ 的元素进行一次操作（减 $1$），数组变为 $[0,2,2,5]$，此时是平衡序列：

因此，答案为 $1$。