调用一个数组 好 如果对于每个长度至少为 $$$2$$$ 的子数组$$$^{\text{∗}}$$$,偶数索引处的元素之和(相对于 原始数组) 大于或等于奇数索引处的元素之和。数组索引从$$$1$$$开始。
例如,数组 $$$[3,8,4,4]$$$ 和 $$$[2,3,1,4,2]$$$ 就很好。数组$$$[0,2,4,1]$$$不是,因为在子数组$$$[2,4,1]$$$中,原始数组中偶数索引处的元素是$$$2$$$(索引$$$2$$$)和$$$1$$$(索引$$$4$$$),而奇数索引处的唯一元素是$$$4$$$(索引$$$3$$$)。由于 $$$2 + 1 \lt 4$$$,条件确实 不 保留该子数组。
给你一个 $$$n$$$ 数组 非负 整数 $$$a_1,a_2,\ldots,a_n$$$。在一次操作中,您可以将数组中的任何元素减少 $$$1$$$,但所有元素必须保留 非负。您的任务是找到使数组 $$$a$$$ 良好所需的最少操作数。可以证明,使用有限次数的操作可以使数组变得良好。
$$$^{\text{*}}$$$数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过从 $$$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$$$ 良好所需的最少操作数。
示例
输入复制
843 8 4 440 2 3 523 152 3 1 4 240 2 4 153 1 4 5 1113 0 5 4 4 5 3 0 3 4 112410748345 10753674 975233308 193331255 893457280 279719251 704970985 412553354 801228787 44181004 1000000000 3829103
输出复制
0 1 2 0 3 6 14 4450984776
注意
在第一个测试用例中,数组 $$$a$$$ 已经很好,所以答案是 $$$0$$$。以下是每个子数组的检查:
| 子数组 | 偶数索引总和 | 奇数索引和 | 满足条件吗? |
| $$$[3,8]$$$ | $$$8$$$ | $$$3$$$ | 是 |
| $$$[8,4]$$$ | $$$8$$$ | $$$4$$$ | 是 |
| $$$[4,4]$$$ | $$$4$$$ | $$$4$$$ | 是 |
| $$$[3,8,4]$$$ | $$$8$$$ | $$$3+4=7$$$ | 是 |
| $$$[8,4,4]$$$ | $$$8+4 = 12$$$ | $$$4$$$ | 是 |
| $$$[3,8,4,4]$$$ | $$$8+4=12$$$ | $$$3 + 4 = 7$$$ | 是 |
在第二个测试用例中,数组 $$$a$$$ 不好:
| 子数组 | 偶数索引总和 | 奇数索引和 | 满足条件吗? |
| $$$[0,2]$$$ | $$$2$$$ | $$$0$$$ | 是 |
| $$$[2,3]$$$ | $$$2$$$ | $$$3$$$ | No |
| $$$[3,5]$$$ | $$$5$$$ | $$$3$$$ | 是 |
| $$$[0,2,3]$$$ | $$$2$$$ | $$$0+3=3$$$ | No |
| $$$[2,3,5]$$$ | $$$2 + 5 = 7$$$ | $$$3$$$ | 是 |
| $$$[0,2,3,5]$$$ | $$$2+5 = 7$$$ | $$$0+3 = 3$$$ | 是 |
但是,如果我们对索引 $$$3$$$ 执行操作,数组将变为 $$$[0,2,2,5]$$$ 并且现在就可以了:
| 子数组 | 偶数索引总和 | 奇数索引和 | 满足条件吗? |
| $$$[0,2]$$$ | $$$2$$$ | $$$0$$$ | 是 |
| $$$[2,2]$$$ | $$$2$$$ | $$$2$$$ | 是 |
| $$$[2,5]$$$ | $$$5$$$ | $$$2$$$ | 是 |
| $$$[0,2,2]$$$ | $$$2$$$ | $$$0+2=2$$$ | 是 |
| $$$[2,2,5]$$$ | $$$2 + 5 = 7$$$ | $$$2$$$ | 是 |
| $$$[0,2,2,5]$$$ | $$$2+5 = 7$$$ | $$$0+2 = 2$$$ | 是 |
因此,答案是$$$1$$$。