题目描述

长度为 $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 翻译

样例

7
5
1 4 2 5 3
4
3 3 2 1
5
6 6 6 6 6
7
1 2 3 4 5 6 7
3
3 2 1
2
1 2
9
65 85 19 53 21 79 92 29 96

0
1
3
6
1
0
13