题目背景

小 H 不会排序，但是会二分！

于是他创造了一个基于二分查找与插入的快速排序。

本题存在可带修做法，因为这题是这场考试的签到题所以良心出题人没有加上。

题目描述

给定一个排列 $p$。每次可以选择一个数 $p_i$，你需要找到最小的 $j$，使得 $j>i$ 且 $p_j>p_i$，并将 $p_i$ 插入到 $p_j$ 前面。你需要最小化使得 $p_i=i$ 的操作次数。

若不存在这样的 $j$，则无法进行操作。

输入格式

第一行一个整数 $n$，表示排列的长度。

接下来一行 $n$ 个整数描述排列 $p$，第 $i$ 个数为 $p_i$。

输出格式

一行一个整数表示最小的操作次数。若无法完成排序输出 $-1$。

5
3 1 4 2 5

2

提示

「本题采用捆绑测试」

• $\texttt{Subtask 1(20pts)：}n\le10$。
• $\texttt{Subtask 2(20pts)：}$保证 $p_i=n-i+1$。
• $\texttt{Subtask 3(20pts)：}n\le1000$。
• $\texttt{Subtask 4(40pts)：}$无特殊性质。

对于全部的数据，$1\le n\le2\times 10^6$，$p$ 是一个 $1$ 到 $n$ 的排列。