1369: 你好，奇偶

长度为 $m$ 的任意整数数组 $b$，如果对于所有 $i$$(1 \leq i < m)$都满足以下条件，则称该数组是令人敬畏的：

• 若 i 是奇数，则 $ (b_i < b_{i+1})$ 成立；
• 若 i 是偶数，则 $(b_i > b_{i+1})$ 成立。

换句话说，数组需满足交替增减的关系：$(b_1 < b_2 > b_3 < b_4 > \dots)$。

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

1. 操作 1：选择一个整数 $i$$(1 \leq i \leq n)$，执行 $(a_i := \max(a_1, \dots, a_i)$（即用前 i 个元素的最大值替换 $(a_i)$；
2. 操作 2：选择一个整数 $i$$(1 \leq i \leq n)$，将 $(a_i)$ 减少 1。

请确定最少需要执行多少次操作 2，才能使数组 $a$ 变得令人敬畏。注意：你不需要最小化操作 1 的执行次数。

1. 每个测试用例的第一行包含一个整数 $n$$(2 \leq n \leq 2 \times 10^5)$，表示数组 $a$ 的长度。
2. 每个测试用例的第二行包含 $n$ 个整数 $(a_1, a_2, \dots, a_n)$$(1 \leq a_i \leq 10^3)$。

对于每个测试用例，输出使数组 $a$ 成为令人敬畏的数组所需的最少操作 2 次数。

9
65 85 19 53 21 79 92 29 96

13