P10155 [LSOT-2] Quicksort Based on Binary Search and Insertion.

Little H cannot sort, but he can do binary search. So he created a quicksort based on binary search and insertion. This problem has a solution that supports modifications, but since this is the check-in problem of this contest, the kind problem setter did not add it.

Given a permutation $p$. Each time, you may choose a number $p_i$. You need to find the smallest $j$ such that $j>i$ and $p_j>p_i$, and insert $p_i$ before $p_j$. You need to minimize the number of operations needed to make $p_i=i$. If no such $j$ exists, then you cannot perform an operation.

The first line contains an integer $n$, representing the length of the permutation. The next line contains $n$ integers describing the permutation $p$, where the $i$-th number is $p_i$.

Output one integer on a single line, representing the minimum number of operations. If it is impossible to finish sorting, output $-1$.

**"This problem uses bundled tests."** - $\texttt{Subtask 1(20pts):}n\le10$. - $\texttt{Subtask 2(20pts):}$guarantee $p_i=n-i+1$. - $\texttt{Subtask 3(20pts):}n\le1000$. - $\texttt{Subtask 4(40pts):}$no special properties. For all testdata, $1\le n\le2\times 10^6$, and $p$ is a permutation of $1$ to $n$. Translated by ChatGPT 5