CFCF2154B.Make it Zigzag

普及-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

长度为 $m$ 的任意整数数组 $b$ 如果对于所有 $i$ （ $1 \le i < m$ ）满足以下条件，则被认为是“awesome”（极棒）的：

换句话说，数组需满足如下不等式： $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$ 的最小次数。

输入#1

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

输出#1

在第一个测试用例中，数组已经是“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$ 次数。