Minimum Operations to Sort by Reversals

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. In one operation, you are allowed to reverse any contiguous subarray of the array.

Formally, given an array \(A = [a_1, a_2, \dots, a_n]\), you may choose two indices \(l\) and \(r\) (with \(1 \le l \le r \le n\)) and reverse the segment \(A[l \dots r]\). Determine the minimum number of such reversal operations needed so that the final array is sorted, i.e. \(a_1 \le a_2 \le \dots \le a_n\).

Example:

Input:
5
4 3 2 5 1
Output:
2

</p>

In the example above, one possible sequence of operations is:

• Reverse the subarray from index 1 to 3: [4, 3, 2] becomes [2, 3, 4], resulting in [2, 3, 4, 5, 1].
• Reverse the subarray from index 4 to 5: [5, 1] becomes [1, 5], resulting in [2, 3, 4, 1, 5].
• Note: There may be other sequences leading to the sorted array. The minimum number of operations needed in this case is 2.

Note: The problem guarantees that it is always possible to sort the array using the allowed reversal operations.

inputFormat

The input is read from standard input (stdin) and consists of two lines:

1. The first line contains a single integer \(n\) \((1 \le n \le 10^5)\), representing the number of elements in the array.
2. The second line contains \(n\) space-separated integers, representing the elements of the array \(A\).

outputFormat

Output a single integer to standard output (stdout) – the minimum number of reversal operations needed to sort the array in non-decreasing order.

## sample

5
4 3 2 5 1

2