CF1861D Sorting By Multiplication

给定一个长度为 $n$ 的数组 $a$，数组中的元素均为正整数。 你可以对该数组进行如下操作任意次（可以为零次）： - 选择三个整数 $l$、$r$ 和 $x$，满足 $1 \le l \le r \le n$，然后将所有满足 $l \le i \le r$ 的 $a_i$ 都乘以 $x$。 注意，你可以选择任意整数作为 $x$，不要求 $x$ 为正数。 你需要计算使数组 $a$ 严格递增（即满足 $a_1 < a_2 < \dots < a_n$）所需的最少操作次数。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$。 输入的额外约束：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

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

在第一个测试用例中，可以按如下方式进行操作： - $l = 2$，$r = 4$，$x = 3$； - $l = 4$，$r = 4$，$x = 2$； - $l = 5$，$r = 5$，$x = 10$。 经过这些操作后，数组 $a$ 变为 $[1, 3, 6, 12, 20]$。 在第二个测试用例中，可以进行如下操作： - $l = 1$，$r = 4$，$x = -2$； - $l = 6$，$r = 6$，$x = 1337$。 经过这些操作后，数组 $a$ 变为 $[-10, -8, -6, -4, 5, 1337]$。 在第三个测试用例中，数组 $a$ 已经是严格递增的。 由 ChatGPT 4.1 翻译