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 翻译