CF2154B Make it Zigzag

长度为 $m$ 的任意整数数组 $b$ 如果对于所有 $i$（$1 \le i < m$）满足以下条件，则被认为是“awesome”（极棒）的： - 如果 $i$ 是奇数，则 $b_i < b_{i+1}$。 - 如果 $i$ 是偶数，则 $b_i > b_{i+1}$。 换句话说，数组需满足如下不等式：$b_1 < b_2 > b_3 < b_4 \ldots$ 给定一个长度为 $n$ 的正整数数组 $a$。你可以按照任意顺序、任意多次执行以下两种操作： - 操作 $1$：选择一个整数 $i$（$1 \le i \le n$），令 $a_i := \max(a_1, \ldots, a_i)$，即将 $a_i$ 替换为前缀最大值。 - 操作 $2$：选择一个整数 $i$（$1 \le i \le n$），然后将 $a_i$ 减少 $1$。 请你求出使 $a$ 成为“awesome”数组所需执行操作 $2$ 的最少次数。注意：你不需要最小化执行操作 $1$ 的次数。

每组测试包含多个测试用例。第一行输入测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来每组测试用例包含： 第一行输入一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示数组 $a$ 的长度。 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le 10^9$）。 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试用例，输出使 $a$ 成为“awesome”数组所需执行操作 $2$ 的最小次数。

在第一个测试用例中，数组已经是“awesome”的，无需任何操作。 在第二个测试用例中，可以按如下方式操作，使 $a$ 成为“awesome”： - 执行一次操作 $2$，将 $a_1$ 减少 $1$：$[\color{red}3, 3, 2, 1] \rightarrow [\color{red}2, 3, 2, 1]$。 - 执行一次操作 $1$，将 $a_4$ 改为 $\max(2, 3, 2, 1) = 3$：$[2, 3, 2, \color{red}1] \rightarrow [2, 3, 2, \color{red}3]$。 $[2, 3, 2, 3]$ 是“awesome”数组，因为 $2 < 3 > 2 < 3$。可以证明，这是使得 $a$ 成为“awesome”数组所需的最少操作 $2$ 次数。 由 ChatGPT 5 翻译