CF2081B Balancing

Ecrade 有一个整数数组 $a_1, a_2, \ldots, a_n$。保证对于每个 $1 \le i < n$，$a_i \neq a_{i+1}$。 Ecrade 可以通过若干次操作将数组变为严格递增的数组。 每次操作中，他可以选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），并将 $a_l, a_{l+1}, \ldots, a_r$ 替换为任意 $r-l+1$ 个整数 $a'_l, a'_{l+1}, \ldots, a'_r$。替换后的数组需要满足以下约束： - 对于每个 $l \le i < r$，$a'_i$ 和 $a'_{i+1}$ 之间的比较关系必须与原数组中 $a_i$ 和 $a_{i+1}$ 的比较关系相同。即，若原数组中 $a_i < a_{i+1}$，则替换后必须有 $a'_i < a'_{i+1}$；若原数组中 $a_i > a_{i+1}$，则替换后必须有 $a'_i > a'_{i+1}$；若原数组中 $a_i = a_{i+1}$，则替换后必须有 $a'_i = a'_{i+1}$。 Ecrade 想知道使数组严格递增所需的最少操作次数。由于问题有一定难度，请你帮助他！

每个测试包含多个测试用例。第一行输入测试用例数量 $t$（$1 \le t \le 10^4$）。接下来描述每个测试用例。 每个测试用例的第一行输入一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。 每个测试用例的第二行输入 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^9 \le a_i \le 10^9$）。 保证对于每个 $1 \le i < n$，$a_i \neq a_{i+1}$。 保证所有测试用例的 $n$ 总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数表示使数组严格递增所需的最少操作次数。

第一个测试用例中，一种获得最少操作次数的方式为： 1. 第一次操作选择 $l = 2, r = 2$，将 $a'_2 = 4$，此时数组变为 $[3, 4, 1]$； 2. 第二次操作选择 $l = 1, r = 2$，将 $a'_1 = -1, a'_2 = 0$，此时数组变为 $[-1, 0, 1]$。 第二个测试用例中，一种获得最少操作次数的方式为： 1. 第一次操作选择 $l = 2, r = 3$，将 $a'_2 = 4, a'_3 = 5$，此时数组变为 $[3, 4, 5]$。 第三个测试用例中，一种获得最少操作次数的方式为： 1. 第一次操作选择 $l = 2, r = 3$，将 $a'_2 = -1, a'_3 = 1$，此时数组变为 $[-2, -1, 1, 2]$。 翻译由 DeepSeek R1 完成