奇怪的排序

题目描述

qxforever 喜欢排序。

他有一个长度为 $n$ 的排列 $P$ ( $[p_1,p_2,\cdots,p_n]$ ) 。即在一个长度为 $n$ 的数组中，$1$ 到 $n$ 的正整数的出现次数均为 $1$ 。例如，$[2,3,1,5,4]$ 是一个排列，而 $[1,2,2]$ 不是一个排列。

现在你需要进行以下的操作直到该排列变为 $[1,2,3,\cdots,n]$ ：

• 首先，给出关于极大元 和非极大元 的定义。$p_i$ 是极大元当且仅当 $p_i$ 是 $1$ 到 $i$ 中最大的元素，即 $p_i=\max_{j=1}^ip_j$ 。否则，$p_i$ 是非极大元。
• 设 $a_1,a_2,\dots,a_k$ 是在 $P$ 中出现的极大元，$b_1,b_2,\dots,b_{n-k}$ 是在 $P$ 中出现的非极大元。我们将 $P$ 重排为 $[ b_1,b_2,\dots,b_{n-k},a_1,a_2,\dots,a_k]$ 。

qxforever 想知道最少多少次操作之后，$P$ 能变为 $[1,2,3,\cdots,n]$ 。

输入

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

第二行包含 $n$ 个正整数，$p_1,p_2,\dots,p_n$ 表示 $P$ 的 $n$ 个元素。保证输入是一个合法的排列。

输出

一个整数，表示 $P$ 变为 $[1,2,3,\cdots,n]$ 需要的最少的次数。

输入样例1

5
3 5 1 2 4

输出样例1

3

第一次操作中，$3,5$ 是极大元，$1,2,4$ 是非极大元，排列变为 $[1,2,4,3,5]$ 。

$[3,5,1,2,4]$ >> $[1,2,4,3,5]$ >> $[3,1,2,4,5]$ >> $[1,2,3,4,5]$ 需要 $3$ 次。

输入样例2

5
5 4 3 2 1

输出样例2

4

[$5,4,3,2,1$] >> $[4,3,2,1,5]$ >> $[3,2,1,4,5]$ >> $[2,1,3,4,5]$ >> $[1,2,3,4,5]$ 需要 $4$ 次。

数据范围与约定

对于 $10\%$ 的数据，满足 $n\le 10$。

对于 $40\%$ 的数据，满足 $n\le 5000$。

对于 $100\%$ 的数据，满足 $n\le 2\times10^5$ 。