CF1861D.Sorting By Multiplication

You are given an array $a$ of length $n$, consisting of positive integers.

You can perform the following operation on this array any number of times (possibly zero):

• choose three integers $l$, $r$ and $x$ such that $1 \le l \le r \le n$, and multiply every $a_i$ such that $l \le i \le r$ by $x$.

Note that you can choose any integer as $x$, it doesn't have to be positive.

You have to calculate the minimum number of operations to make the array $a$ sorted in strictly ascending order (i. e. the condition $a_1 \lt a_2 \lt \dots \lt a_n$ must be satisfied).

给你一个长度为 $n$ 的数组 $a$，其中所有元素均为正整数。

你可以对这个数组执行以下操作任意次（可以为零次）：

• 选择三个整数 $l$、$r$ 和 $x$，满足 $1 \le l \le r \le n$，并将所有下标 $i$ 满足 $l \le i \le r$ 的元素 $a_i$ 同时乘以 $x$。

注意：$x$ 可以是任意整数，不一定是正数。

你需要计算使数组 $a$ 严格递增（即满足 $a_1 \lt a_2 \lt \dots \lt a_n$）所需的最少操作次数。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

Additional constraint on the input: the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

For each test case, print one integer — the minimum number of operations required to make $a$ sorted in strictly ascending order.

对于每个测试用例，输出一个整数——使 $a$ 严格升序排列所需的最少操作次数。

In the first test case, we can perform the operations as follows:

• $l = 2$, $r = 4$, $x = 3$;
• $l = 4$, $r = 4$, $x = 2$;
• $l = 5$, $r = 5$, $x = 10$.

After these operations, the array $a$ becomes $[1, 3, 6, 12, 20]$.

In the second test case, we can perform one operation as follows:

• $l = 1$, $r = 4$, $x = -2$;
• $l = 6$, $r = 6$, $x = 1337$.

After these operations, the array $a$ becomes $[-10, -8, -6, -4, 5, 1337]$.

In the third test case, the array $a$ is already sorted.

在第一个测试用例中，我们可以执行如下操作：

• $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$ 已经是有序的。