Permutation Identity Minimization

Given a permutation \(p\) of \(n\) distinct integers from 1 to \(n\) (1-indexed), you are allowed to perform the following operation:

• Choose an index \(i\) (1-indexed) such that there exists an index \(j\) with \(j > i\) and \(p_j > p_i\). Let \(j\) be the smallest index greater than \(i\) satisfying \(p_j > p_i\).
• Remove \(p_i\) from its current position and insert it immediately before \(p_j\). Formally, if you denote the permutation as a list, then the operation rotates the subarray \( [p_i, p_{i+1}, \ldots, p_j] \) into \( [p_{i+1}, \ldots, p_j, p_i] \).

Your goal is to achieve the identity permutation, i.e. a permutation where for every index \(i\) the equality \(p_i = i\) holds. Compute the minimum number of allowed operations required to obtain the identity permutation. If it is impossible to achieve the identity permutation using these operations, output \(-1\).

Note: The indices are 1-indexed and all formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains an integer \(n\) (the size of the permutation). The second line contains \(n\) space‐separated integers representing the permutation \(p\). It is guaranteed that \(p\) is a permutation of \(\{1, 2, \ldots, n\}\).

outputFormat

Output a single integer representing the minimum number of operations required to transform the given permutation into the identity permutation \((1, 2, \ldots, n)\). If it is impossible, output \(-1\).

sample

3
2 1 3

1