长度为 $$$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$$$ 很棒的最小成本。
示例
输入复制
751 4 2 5 343 3 2 156 6 6 6 671 2 3 4 5 6 733 2 121 2965 85 19 53 21 79 92 29 96
输出复制
01361013
注意
在第一个测试用例中,数组已经很棒,因此不需要执行任何操作。
在第二个测试用例中,$$$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]$$$。