310622: CF1861D. Sorting By Multiplication

D. Sorting By Multiplicationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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 < a_2 < \dots < a_n$ must be satisfied).

Input

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$.

Output

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

ExampleInput

3
5
1 1 2 2 2
6
5 4 3 2 5 1
3
1 2 3

Output

3
2
0

Note

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.

题目大意：
给定一个由正整数组成的长度为n的数组a。可以执行以下操作任意次数（可能为零）：选择三个整数l、r和x，使得1≤l≤r≤n，并将每个满足l≤i≤r的ai乘以x。注意，可以选择任何整数作为x，它不一定是正数。需要计算使数组a按严格递增顺序排序所需的最小操作数（即满足条件a1 < a2 < ... < an）。

输入输出数据格式：
输入格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——数组a的长度。
每个测试用例的第二行包含n个整数a1,a2,...,an（1≤ai≤10^9）——数组a。
输入附加限制：所有测试用例的n之和不超过2×10^5。

输出格式：
对于每个测试用例，打印一个整数——使a按严格递增顺序排序所需的最小操作数。题目大意： 给定一个由正整数组成的长度为n的数组a。可以执行以下操作任意次数（可能为零）：选择三个整数l、r和x，使得1≤l≤r≤n，并将每个满足l≤i≤r的ai乘以x。注意，可以选择任何整数作为x，它不一定是正数。需要计算使数组a按严格递增顺序排序所需的最小操作数（即满足条件a1 < a2 < ... < an）。 输入输出数据格式： 输入格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——数组a的长度。 每个测试用例的第二行包含n个整数a1,a2,...,an（1≤ai≤10^9）——数组a。 输入附加限制：所有测试用例的n之和不超过2×10^5。 输出格式： 对于每个测试用例，打印一个整数——使a按严格递增顺序排序所需的最小操作数。