Minimum Moves to Sort Array via Subarray Reversal

You are given an array of n integers. In one move, you can reverse any continuous subarray of the array. Your task is to determine the minimum number of moves required to sort the array in non-decreasing order. The array is considered sorted if $$a_1 \leq a_2 \leq \cdots \leq a_n$$. It can be shown that the answer is always 0, 1, or 2.

In other words, find the minimum number of moves needed to transform the given array into its sorted order by reversing one or more continuous segments.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10^5), the number of elements in the array. The second line contains n space-separated integers $$a_1, a_2, \dots, a_n$$ (where $$|a_i| \leq 10^9$$).

outputFormat

Output a single integer representing the minimum number of moves required to sort the array in non-decreasing order.## sample

5
1 2 3 4 5

0