Minimum Subarray Reversal Moves

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 choosing a contiguous segment of the array and reversing the order of the elements in that segment. The allowed number of moves is based on the following observations:

• If the array is already sorted, no moves are required.
• If by reversing a single contiguous subarray the entire array becomes sorted, then the answer is 1.
• Otherwise, the answer is 2.

For example:

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

The desired function should implement the following logic:

if arr == sorted(arr):
    return 0
else:
    l = index of first differing element from the left
    r = index of first differing element from the right
    if reversing arr[l...r] makes arr sorted:
         return 1
    else:
         return 2

In the case where more than one reversal is necessary, simply output 2.

All formulas and key expressions are given below in LaTeX format:

If the array is already sorted, then \(\text{moves} = 0\). Otherwise, let \(l\) be the smallest index and \(r\) be the largest index such that \(a_l \neq a_l^*\) and \(a_r \neq a_r^*\) where \(a^*\) is the sorted array. If \(\text{reverse}(a[l:r+1]) = a^*[l:r+1]\), then \(\text{moves} = 1\); otherwise, \(\text{moves} = 2\).

inputFormat

The input is read from standard input (stdin) and has the following format:

T
a1 a2 ... aT

Where:

• T is a positive integer that represents the number of elements in the array.
• a₁, a₂, ..., a_T are the integer elements of the array, separated by spaces.

outputFormat

Output a single integer to the standard output (stdout) which represents the minimum number of subarray reversals required to sort the array in non-decreasing order.

## sample

5
1 2 3 4 5

0