Minimum Flips to Sort

You are given an array of n integers. The task is to determine the minimum number of flips required to sort the array in non-decreasing order. A flip is defined as reversing a contiguous subarray. More specifically, if the array is not already sorted, identify the first and last positions where the array differs from its sorted order. If flipping the subarray between these indices sorts the array, then the answer is 1; otherwise, the answer is 2. Formally, let \(a\) be the original array and \(s = sorted(a)\). If \(a = s\), then the minimum flips is 0. Otherwise, let \(i\) be the smallest index and \(j\) be the largest index such that \(a_i \neq s_i\) and \(a_j \neq s_j\). If reversing the subarray from \(i\) to \(j\) yields \(s\), the answer is 1; else, it is 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 denoting the elements of the array.

Example:

5
3 2 1 4 5

outputFormat

Output a single integer representing the minimum number of flips required so that the array becomes sorted in non-decreasing order.

Example:

1

5
3 2 1 4 5

1