CF2134C Even Larger

一个数组被称为“好数组”，如果对于其任意长度不少于 $2$ 的子数组，位于原数组偶数下标（下标从 $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 < 4$，因此该子数组不满足条件。 给定一个长度为 $n$ 的非负整数数组 $a_1,a_2,\ldots,a_n$。每次操作，你可以将数组中的任意一个元素减 $1$，但所有元素必须保持非负。你的任务是求出使得数组 $a$ 变成“好数组”所需的最少操作次数。可以证明一定存在有限次操作使数组变成好数组。 数组 $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$ 变为“好数组”所需的最少操作次数。

在第一个测试用例中，数组 $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$ | 否 | | $[3,5]$ | $5$ | $3$ | 是 | | $[0,2,3]$ | $2$ | $0+3=3$ | 否 | | $[2,3,5]$ | $2+5=7$ | $3$ | 是 | | $[0,2,3,5]$ | $2+5=7$ | $0+3=3$ | 是 | 但是，如果我们对下标 $3$ 的元素进行一次操作（减 $1$），数组变为 $[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$。 由 ChatGPT 5 翻译