CF2081B Balancing

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