题目描述

数组 $b$ 的长度为 $m$，若对所有 $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\ldots$ 的交替关系。

给定长度为 $n$ 的正整数数组 $a$。你可以任意次、按任意顺序执行下列两种操作：

• 操作 1：选择一个整数 $i\ (1\le i\le n)$ 并令 $a_i:=\max(a_1,\dots,a_i)$，即将 $a_i$ 替换为其前缀最大值；
• 操作 2：选择一个整数 $i\ (1\le i\le n)$ 并将 $a_i$ 减 $1$（即 $a_i:=a_i-1$）。

问：在允许任意次执行操作 1 的前提下，使数组 $a$ 变为 awesome，需要 最少 执行操作 2 的次数是多少？（注意不需要最小化操作 1 的次数，仅最小化操作 2 的总次数。）

输入格式

• 第 $1$ 行：一个整数 $t$，表示测试用例个数。

• 接下来对每个测试用例，使用 两行 表示：

  • 第 $1$ 行：一个整数 $n$（数组长度）。
  • 第 $2$ 行：$n$ 个整数 $a_1,a_2,\dots,a_n$（用空格分隔）。

输出格式

对每个测试用例输出一行，包含一个整数 —— 使数组 $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

说明

样例解释

• 第一个样例：数组已满足交替关系，无需操作 $2$，答案为 $0$。
• 第二个样例：对 $[3,3,2,1]$，只需一次操作 $2$（例如把 $a_1$ 变为 $2$），再配合若干次操作 $1$ 可得到 $[2,3,2,3]$，此时满足 $2<3>2<3$，因此最少操作 $2$ 次数为 $1$。

数据范围

• $1\le t\le 10^4$；
• 对每个测试用例，$2\le n\le 2\cdot10^5$；
• $1\le a_i\le 10^9$；
• 所有测试用例中 $\sum n\le 2\cdot10^5$。