← Home
write a go solution for Description:
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<=l<=r<=n, and multiply every a_i such that l<=i<=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<...<a_n must be satisfied).

Input Format:
The first line contains a single integer t (1<=t<=10^4)  — the number of test cases.

The first line of each test case contains one integer n (1<=n<=2*10^5)  — the length of the array a.

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

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

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

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.

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

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

In the third test case, the array a is already sorted.. Output only the code with no comments, explanation, or additional text.