Minimum Reverse Operations to Sort Arrays

You are given several arrays. In one operation, you are allowed to reverse the entire array. Your task is to determine the minimum number of reverse operations needed to transform each array into a sorted (non-decreasing) array. An array \(A = [a_1, a_2, \dots, a_n]\) is considered sorted if \(a_1 \le a_2 \le \dots \le a_n\).

Note: In this problem, if the array is already sorted, no operation is needed (answer is 0). Otherwise, one reverse operation is always enough to sort the array (answer is 1).

For example:

• For the array [1, 3, 2, 4], the answer is 1.
• For the array [5, 4, 3, 2, 1], the answer is 1.
• For the array [2, 2, 2], the answer is 0.

inputFormat

The input is read from stdin and consists of multiple test cases. The first line contains an integer \(T\) representing the number of test cases. For each test case, the first line contains an integer \(n\) denoting the number of elements in the array. The next line contains \(n\) integers separated by spaces representing the array elements.

outputFormat

For each test case, output a single line containing one integer: the minimum number of reverse operations needed to sort the array.

## sample

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

1
1
0

</p>