Permutation Sorting with Quadruple Splitting

You are given a permutation \(p_1, p_2, \ldots, p_n\) of the numbers \(1\) to \(n\). You can perform the following operation any number of times (including zero):

• Divide the permutation \(p\) into four (possibly empty) contiguous segments: \(a, b, c, d\). Then, reorder these segments as \(c, a, d, b\).

Your task is to determine the minimum number of operations needed to transform the given permutation into the sorted order \(1, 2, \ldots, n\).

Note: If the permutation is already sorted, the answer is 0.

Operation Explanation: Suppose the current permutation is represented as an array. Choose two or three indices \(0 \le i \le j \le k \le n\) such that the segments are defined as follows:

[ \text{a} = p[0,i), \quad \text{b} = p[i,j), \quad \text{c} = p[j,k), \quad \text{d} = p[k,n). ]

After the operation, the new permutation becomes \(c\) concatenated with \(a\) concatenated with \(d\) concatenated with \(b\):

[ c,a,d,b. ]

inputFormat

The first line contains an integer \(n\) representing the size of the permutation. The second line contains \(n\) space-separated integers representing the permutation \(p_1, p_2, \ldots, p_n\).

outputFormat

Output a single integer representing the minimum number of operations required to transform the permutation into the sorted order \(1, 2, \ldots, n\).

sample

3
1 2 3

0