← 返回题目列表

Codeforces · 2154/B

B. 使其呈之字形

中文机器翻译题面 查看原题

长度为 $$$m$$$ 的任意整数数组 $$$b$$$ 被认为是很棒的,如果对于所有 $$$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$$$

给你一个正整数数组$$$a$$$,长度为$$$n$$$。您可以按任意顺序执行以下任一操作任意次数:

  • 操作$$$1$$$:选择一个整数$$$i$$$ ($$$1 \le i \le n$$$) 并执行:$$$a_i := \max(a_1,\ldots,a_i)$$$,即将$$$a_i$$$替换为前缀max,最大可达$$$i$$$。
  • 操作$$$2$$$:选择一个整数$$$i$$$ ($$$1 \le i \le n$$$),然后将$$$a_i$$$减$$$1$$$。

确定要使 $$$a$$$ 变得很棒,需要执行操作 $$$2$$$ 的最少次数。请注意,你这样做 不 需要尽量减少执行操作$$$1$$$的次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

对于每个测试用例,输出使 $$$a$$$ 很棒的最小成本。

示例

输入
复制

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

注意

在第一个测试用例中,数组已经很棒,因此不需要执行任何操作。

在第二个测试用例中,$$$a$$$ 可以变得很棒,如下所示:

  • 使用操作$$$2$$$并将$$$a_1$$$减少$$$1$$$。 $$$[\color{红色}3, 3, 2, 1] \rightarrow [\color{红色}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]$$$ 非常棒,因为 $$$2 \lt 3 \gt 2 \lt 3$$$。可以证明,这是$$$2$$$操作需要执行的最少次数。