Minimum Cuts for Sorting a Permutation

JokerShaco has a permutation \(p\) of length \(n\) (i.e. a sequence containing every integer from \(1\) to \(n\) exactly once). He wants to transform \(p\) into the sorted permutation \( [1, 2, \dots, n] \) by performing the following operations:

• Cut: Partition the permutation into one or more contiguous segments (each segment must contain at least one element). Note that you may choose not to cut at all, in which case the entire permutation is a single segment.
• Reverse: Choose some of these segments and reverse them. Reversal of a segment \([a_1,a_2,\dots,a_m]\) yields \([a_m,a_{m-1},\dots,a_1]\).
• Reorder: Rearrange the segments in any order and concatenate them.

After optionally reversing some segments, each segment must appear in increasing order so that when reordering the segments, the final sequence becomes \(1,2,\dots,n\). Notice that for a segment to be made increasing by at most one reversal, it must originally be either strictly increasing or strictly decreasing. Moreover, the set of numbers in each segment must form a set of consecutive integers. In other words, for any segment spanning indices \(i\) to \(j\) (with length \(L=j-i+1\)), if \(mn\) and \(mx\) are the minimum and maximum values in that segment, then it must hold that:

[ mx - mn = L - 1. ]

Your task is to determine the minimum number of cuts required (note that if the permutation is divided into \(k\) segments, then the number of cuts made is \(k-1\)) so that by possibly reversing some segments and then reordering them, the permutation can be rearranged into sorted order.

Input Format: The input begins with an integer \(n\) (the length of the permutation) followed by \(n\) space separated integers which represent the permutation \(p\).

Output Format: Output a single integer representing the minimum number of cuts required.

Example:

Input:
3
2 3 1

Output:
1

inputFormat

The first line contains an integer \(n\) denoting the length of the permutation. The second line contains \(n\) space-separated integers representing the permutation \(p\).

outputFormat

Output a single integer: the minimum number of cuts required so that after possibly reversing some segments and then reordering them, the permutation becomes sorted in increasing order.

sample

3
3 2 1

0