CF2154B.Make it Zigzag

An arbitrary array of integers $b$ of length $m$ is considered awesome if for all $i$ ($1 \le i \lt m$):

• if $i$ is odd then $b_i \lt b_{i + 1}$ holds.
• if $i$ is even then $b_i \gt b_{i + 1}$ holds.

In other words, the following inequality is true: $b_1 \lt b_2 \gt b_3 \lt b_4 \ldots$

You are given an array of positive integers $a$ of length $n$. You may do either of the following operations any number of times, in any order:

• operation $1$: select an integer $i$ ($1 \le i \le n$) and do: $a_i := \max(a_1,\ldots,a_i)$, that is, replace $a_i$ with the prefix max up to $i$.
• operation $2$: select an integer $i$ ($1 \le i \le n$) and then decrease $a_i$ by $1$.

Determine the minimum number of times you need to do operation $2$ to make $a$ awesome. Note that you do not need to minimise the number of times you perform operation $1$.

一个长度为 $m$ 的任意整数数组 $b$ 被称为“极好”（awesome），当且仅当对所有 $i$（$1 \le i \lt m$）满足：

• 若 $i$ 为奇数，则 $b_i \lt b_{i + 1}$；
• 若 $i$ 为偶数，则 $b_i \gt b_{i + 1}$。

换言之，以下不等式成立：$b_1 \lt b_2 \gt b_3 \lt b_4 \ldots$

现给定一个长度为 $n$ 的正整数数组 $a$。你可以以任意顺序、任意次数执行以下两种操作之一：

• 操作 $1$：选择一个整数 $i$（$1 \le i \le n$），并令 $a_i := \max(a_1,\ldots,a_i)$，即用前缀最大值（从 $a_1$ 到 $a_i$ 的最大值）替换 $a_i$；
• 操作 $2$：选择一个整数 $i$（$1 \le i \le n$），然后将 $a_i$ 减 $1$。

请确定为使 $a$ 变为“极好”数组所需执行操作 $2$ 的最小次数。注意：你无需最小化操作 $1$ 的执行次数。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1 \le a_i \le 10^9$).

The sum of $n$ across all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$（$1 \le a_i \le 10^9$）。

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

For each testcase, output the minimum cost to make $a$ awesome.

对于每个测试用例，输出使 $a$ 变为“卓越数”（awesome）的最小代价。

In the first test case, the array is already awesome so no operations need to be done.

In the second test case, $a$ can be made awesome as follows:

• use operation $2$ and decrease $a_1$ by $1$. $[\color{red}3, 3, 2, 1] \rightarrow [\color{red}2, 3, 2, 1]$.
• use operation $1$ and change $a_4$ to $\max(2, 3, 2, 1) = 3$. $[2, 3, 2, \color{red}1] \rightarrow [2, 3, 2, \color{red}3]$.

$[2, 3, 2, 3]$ is awesome as $2 \lt 3 \gt 2 \lt 3$. It can be proven that this is the minimum number of times operation $2$ needs to be performed.

在第一个测试用例中，数组已经是“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 \lt 3 \gt 2 \lt 3$。可以证明，这是所需执行操作 $2$ 的最少次数。