Minimum Operations to Sort

You are given an array of n integers. You are allowed to perform the following operation: choose a continuous subarray and reverse it. Your task is to determine the minimum number of such operations needed to sort the entire array in ascending order.

The answer is always one of the following:

• 0, if the array is already sorted.
• 1, if there exists a contiguous subarray which when reversed makes the entire array sorted.
• 2, otherwise.

A useful observation is that if the array is not sorted, by examining the first and last indices where the array differs from its sorted version, one can decide whether a single reversal suffices. If reversing the subarray between these two indices yields a sorted sequence, then just one operation is needed; otherwise, two operations are necessary.

Mathematically, let (a = [a_1, a_2, \dots, a_n]) be the input array and (s = sorted(a)) be the sorted array. If (a = s), then answer = 0. Otherwise, let (l) be the smallest index and (r) the largest index such that (a_l \neq s_l) and (a_r \neq s_r). If [ a[l \ldots r] = \text{reverse}(sorted(a[l \ldots r])), ] then answer = 1, else answer = 2.

inputFormat

The first line contains an integer (n) representing the number of elements in the array. The second line contains (n) space-separated integers, representing the array elements.

outputFormat

Output a single integer denoting the minimum number of operations required to sort the array in ascending order.## sample

5
1 2 3 4 5

0