Minimum Subarray Reversal to Sort

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

In this problem, you can reverse one contiguous subarray (if needed) so that after the reversal the entire array becomes sorted. Note that if the array is already sorted, no reversal is required.

If the given array is already sorted, then the answer is \(0\). Otherwise, under the constraints of this problem, it is always possible to make the array sorted with a single reversal operation, so the answer should be \(1\).

Formal Explanation:

Let the array be \(A = [a_1, a_2, \dots, a_N]\) and let \(A_\text{sorted}\) denote the sorted array. If \(A = A_\text{sorted}\), output \(0\). Otherwise, there exists indices \(i\) and \(j\) with \(1 \leq i < j \leq N\) such that reversing the subarray \(A[i \dots j]\) makes the array sorted, so output \(1\).

inputFormat

The input is given via stdin and consists of two lines:

1. The first line contains an integer \(N\) representing the number of elements in the array.
2. The second line contains \(N\) space-separated integers denoting the array \(A\).

outputFormat

Output a single integer via stdout which is \(0\) if the array is already sorted, or \(1\) if one subarray reversal is needed to sort the array.

6
3 1 2 4 5 6

1