Minimum Subarray Reversal to Sort Array

You are given an array of integers. Your task is to determine the minimum number of subarray reversals required to sort the array in non-decreasing order.

A subarray reversal means selecting a contiguous segment of the array and reversing its order. In this problem, it turns out that if the given array is not already sorted in non-decreasing order, one reversal is always sufficient to sort the array. More formally, let \(A = [a_1, a_2, \ldots, a_N]\). The answer is:

[ f(A)= \begin{cases} 0, & \text{if } A \text{ is sorted (i.e. } a_1 \le a_2 \le \ldots \le a_N\text{)};\ 1, & \text{otherwise.} \end{cases} ]

This may seem surprising but it holds for all test cases under this problem's constraints. Read the input, process each test case, and output the result for each.

inputFormat

The input is read from standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case, the first line contains an integer (N) (the number of elements in the array), followed by a line with (N) space-separated integers representing the array.

outputFormat

For each test case, output a single integer on a new line, representing the minimum number of subarray reversals required to sort the array in non-decreasing order.## sample

1
5
1 2 3 4 5

0