Minimum Subarray Reversals

You are given an integer n and an array a of n distinct integers which is a permutation of [1, 2, ..., n]. In one operation, you can reverse any contiguous subarray of a. Your task is to determine the minimum number of subarray reversals required to sort the array in increasing order.

The solution employs a greedy approach: find the first index at which the current array differs from the sorted target array. Then reverse the subarray from this index to the position where the correct element is located. Continue until the array is sorted.

Formally, let \(a = [a_1, a_2, \ldots, a_n]\) and \(target = [1, 2, \ldots, n]\). In each operation, find the smallest index \(i\) such that \(a_i \neq i\) and then let \(j\) be the index where \(a_j = i\). Reverse the segment \(a_i, a_{i+1}, \ldots, a_j\). Repeat this until \(a = target\). Output the number of reversals performed.

inputFormat

The input is given from standard input containing two lines:

1. The first line contains a positive integer n (\(1 \leq n \leq 10^5\)), representing the number of elements in the array.
2. The second line contains n space-separated integers representing a permutation of the integers from 1 to n.

outputFormat

Output a single integer representing the minimum number of subarray reversals required to sort the array in increasing order. The result should be written to standard output.

## sample

5
3 1 4 5 2

3

</p>