B. 使其变成锯齿形

每个测试的时间限制：1.5 秒
每个测试的内存限制：256 兆字节

如果一个长度为 $m$ 的任意整数数组 $b$ 满足：对于所有 $i\ (1 \le i < m)$，

• 若 $i$ 是奇数，则 $b_i < b_{i+1}$；
• 若 $i$ 是偶数，则 $b_i > b_{i+1}$；

则称数组 $b$ 是awesome（极好的）。
换句话说，不等式 $b_1 < b_2 > b_3 < b_4 > \dots$ 成立。

你有一个长度为 $n$ 的正整数数组 $a$。
你可以任意多次执行以下两种操作，顺序不限：

1. 操作 1：选择一个下标 $i\ (1 \le i \le n)$，并执行
   $a_i := \max(a_1, \dots, a_i)$，即将 $a_i$ 替换为到 $i$ 为止的前缀最大值。
2. 操作 2：选择一个下标 $i\ (1 \le i \le n)$，然后将 $a_i$ 减少 $1$。

你需要最小化操作 2 的次数，使得数组 $a$ 变成 awesome。
注意：你不需要最小化操作 1 的次数。

输入格式

每个测试包含多个测试用例。
第一行输入一个整数 $t\ (1 \le t \le 10^4)$，表示测试用例的数量。

接下来每个测试用例的输入格式如下：

• 第一行输入一个整数 $n\ (2 \le n \le 2 \cdot 10^5)$，表示数组 $a$ 的长度。
• 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n\ (1 \le a_i \le 10^9)$。

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

输出格式

对于每个测试用例，输出使数组 $a$ 变成 awesome 所需的最少操作 2 的次数。

示例

输入：

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

示例解释

• 第一个测试用例：数组已经是 awesome，所以不需要任何操作。
• 第二个测试用例：可以通过以下步骤使数组变成 awesome：
  1. 使用操作 2，将 $a_1$ 减少 1：$[3,3,2,1] \to [2,3,2,1]$
  2. 使用操作 1，将 $a_4$ 改为 $\max(2,3,2,1) = 3$：$[2,3,2,1] \to [2,3,2,3]$
     得到 $[2,3,2,3]$，满足 $2 < 3 > 2 < 3$。
     可以证明这是最少的操作 2 次数。