Minimum Reversal Operations to Sort Array

You are given an array of n integers. Your task is to determine the minimum number of operations required to sort the array in non-decreasing order, where in one operation you are allowed to reverse any contiguous subarray. If the array is already sorted, no operation is needed.

Note that based on the constraints of this problem, it is guaranteed that if the array is not already sorted, then a single reversal operation is always sufficient to sort the array.

Formally, given an integer n and an array a[1 ... n], output 0 if the array is sorted in non-decreasing order; otherwise, output 1.

The problem may include arrays with repeated elements.

inputFormat

The first line of input contains a single integer n (1 ≤ n ≤ 10⁵), the number of elements in the array. The second line contains n space-separated integers a₁, a₂, ..., a_n (|a_i| ≤ 10⁹). Input is read from standard input (stdin).

outputFormat

Output a single integer which is the minimum number of reversal operations required to sort the array. Output is written to standard output (stdout).

## sample

5
3 1 2 4 5

1

</p>