Background

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.

Problem Description

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.

Input Format

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 Format

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

5
3 1 4 2 5

2

Hint

"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