Minimum Reversal Operations to Sort an Array

You are given an integer n and 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 can choose any subarray and reverse its elements.

Key Observation: The answer can be computed as the number of sorted segments in the array minus one. A sorted segment is defined as a maximal contiguous block that is already sorted in non-decreasing order. More formally, if the array has segments \(S_1, S_2, \dots, S_k\) such that each segment is non-decreasing, then the minimum number of reversal operations required is \(k-1\).

For instance, consider the array [3, 1, 4, 2]: it can be divided into two segments [3, 1] and [4, 2] (since 1 < 3 indicates a new segment), so the answer is 1. However, note that the sample test cases provided in the examples below determine the answer slightly differently based on the exact segmentation approach. Follow the examples carefully.

inputFormat

The first line of input contains an integer n (\(1 \le n \le 10^5\)), the number of elements in the array.

The second line contains n space-separated integers representing the elements of the array.

outputFormat

Output a single integer, the minimum number of operations needed to sort the array in non-decreasing order by reversing subarrays.

4
1 2 3 4

0