B. Balancing
greedy
Ecrade has an integer array \(a_1, a_2, \ldots, a_n\). It's guaranteed that for each \(1 \le i < n\), \(a_i \neq a_{i+1}\).Ecrade can perform several operations on the array to make it strictly increasing.In each operation, he can choose two integers \(l\) and \(r\) (\(1 \le l \le r \le n\)) and replace \(a_l, a_{l+1}, \ldots, a_r\) with any \(r-l+1\) integers \(a'_l, a'_{l+1}, \ldots, a'_r\) satisfying the following constraint: For each \(l \le i < r\), the comparison between \(a'_i\) and \(a'_{i+1}\) is the same as that between \(a_i\) and \(a_{i+1}\), i.e., if \(a_i < a_{i + 1}\), then \(a'_i < a'_{i + 1}\); otherwise, if \(a_i > a_{i + 1}\), then \(a'_i > a'_{i + 1}\); otherwise, if \(a_i = a_{i + 1}\), then \(a'_i = a'_{i + 1}\). Ecrade wants to know the minimum number of operations to make the array strictly increasing. However, it seems a little difficult, so please help him!
Each test contains multiple test cases. The first line contains the number of test cases \(t\) (\(1 \le t \le 10^4\)). The description of the test cases follows. The first line of each test case contains a single integer \(n\) (\(2 \le n \le 2 \cdot 10^5\)).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(-10^9 \le a_i \le 10^9\)).It is guaranteed that for each \(1 \le i< n\), \(a_i \neq a_{i+1}\).It is guaranteed that the sum of \(n\) across all test cases does not exceed \(2 \cdot 10^5\).
For each test case, output a single integer representing the minimum number of operations to make the array strictly increasing.
In the first test case, a possible way to obtain the minimum number of operations: In the first operation, choose \(l = 2, r = 2\) and \(a'_2 = 4\), then \(a=[3, 4, 1]\); In the second operation, choose \(l = 1, r = 2\) and \(a'_1 = -1, a'_2 = 0\), then \(a=[-1, 0, 1]\). In the second test case, a possible way to obtain the minimum number of operations: In the first operation, choose \(l = 2, r = 3\) and \(a'_2 = 4, a'_3 = 5\), then \(a = [3, 4, 5]\). In the third test case, a possible way to obtain the minimum number of operations: In the first operation, choose \(l = 2, r = 3\) and \(a'_2 = -1, a'_3 = 1\), then \(a = [-2, -1, 1, 2]\).