Sorting By Multiplication
Contest: Educational Codeforces Round 154 (Rated for Div. 2)
Difficulty rating: 1800
Tags: dp, greedy

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 format:
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 format:
For each test case, print one integer — the minimum number of operations required to make $$$a$$$ sorted in strictly ascending order.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
3
5
1 1 2 2 2
6
5 4 3 2 5 1
3
1 2 3

Example output:
3
2
0

Editorial:
At first, let's figure out which multiplications by negative values we perform. After a few multiplications, some subarrays of the array $$$a$$$ might become negative. If there is more than one such negative subarray (and there are non-negative elements between them), then the array cannot be sorted by multiplication by non-negative values. If there is one such subarray, then it must be a prefix of the array.
Let's try solving this problem in $$$O(n^2)$$$. Let's iterate over the length of the negative prefix and solve the problem for some fixed negative prefix. Make all the elements on this prefix negative (for example, by multiplying by $$$-1$$$), and then iterate over indices of the array in ascending order. If $$$a_i < a_{i + 1}$$$ (where $$$i$$$ is the current index), then we just go to the next index. Otherwise, we can always multiply the prefix (if $$$a_i < 0$$$) or the suffix (if $$$a_i > 0$$$) by some positive value so that the prefix $$$a_1, \dots, a_i, a_{i + 1}$$$ becomes sorted. Note that if we fixed the negative prefix, we cannot restore the condition $$$a_i < a_{i+1}$$$ on multiple indices $$$i$$$ with just one operation. For example, if $$$a_i, a_{i+1}, a_j$$$ and $$$a_{j+1}$$$ are all positive, $$$a_i \ge a_{i+1}$$$ and $$$a_j \ge a_{j+1}$$$, we need at least two operations to ensure that $$$a_i < a_{i+1}$$$ and $$$a_j < a_{j+1}$$$. In the first operation, we should choose $$$l = i+1$$$, and in the second operation, we should choose $$$l = j+1$$$, so that both $$$a_{i+1}$$$ becomes greater than $$$a_i$$$ and $$$a_{j+1}$$$ becomes greater than $$$a_j$$$.
For example, if the array $$$a$$$ is $$$[-1, -2, -3, 2, 1, 3]$$$ (after we fixed that the first $$$3$$$ elements will be negative). we perform the following sequence of actions:
1. $$$i = 1$$$, $$$a_1 \ge a_2$$$ and $$$a_1 < 0$$$, so we just multiply the prefix $$$a_1, \dots, a_1$$$ by some positive value (for example $$$4$$$); after that the current array $$$a = [-4, -2, -3, 2, 1, 3]$$$;
2. $$$i = 2$$$, $$$a_2 \ge a_3$$$ and $$$a_2 < 0$$$, so we just multiply the prefix $$$a_1, \dots, a_2$$$ by some positive value (for example $$$2$$$); after that the current array $$$a = [-8, -4, -3, 2, 1, 3]$$$;
3. $$$i = 3$$$, $$$a_3 < a_4$$$ so we just go to the next index;
4. $$$i = 4$$$, $$$a_4 \ge a_5$$$ and $$$a_4 > 0$$$, so we just multiply the suffix $$$a_5, \dots, a_6$$$ by some positive value (for example $$$10$$$); after that, the current array $$$a = [-8, -4, -3, 2, 10, 30]$$$;
5. $$$i = 5$$$, $$$a_5 < a_6$$$ so we just go to the next index;
6. $$$i = 6$$$, so the array is sorted.
To solve the problem in $$$O(n)$$$, we need the following observation: if the negative prefix has length $$$x$$$, we perform the operations in two cases:
• if $$$a_i \le a_{i+1}$$$ (in the original array) and $$$i+1 \le x$$$;
• if $$$a_i \ge a_{i+1}$$$ and $$$i \ge x$$$.
So, we can iterate on the length of negative prefix $$$x$$$ and maintain
• the number of indices $$$i$$$ such that $$$a_{i-1} \le a_i$$$ and $$$i < x$$$;
• and the number of indices $$$j$$$ such that $$$a_{j} \ge a_{j+1}$$$ and $$$j \ge x$$$.
Don't forget the case when $$$x = 0$$$, then we don't need an extra operation to make the prefix negative.