题目描述

高桥君非常喜欢排序。

因此，他准备了一个从 $1$ 到 $N$ 的排列 $(p_1, p_2, \ldots, p_N)$，并且他打算反复进行以下操作，直到该排列变成 $(1,2,\ldots,N)$ 为止：

• 首先，对于排列中的每一项 $i$，如果从第 $1$ 项到第 $i$ 项的最大值等于第 $i$ 项本身，则称这一项为「高项」，否则称为「低项」。
• 然后，按照当前排列的顺序，将高项中的数记为 $a_1, a_2, \ldots, a_k$，低项中的数记为 $b_1, b_2, \ldots, b_{N-k}$。
• 最后，将排列重新排列为 $(b_1, b_2, \ldots, b_{N-k}, a_1, a_2, \ldots, a_k)$。

请你求出高桥君完成排序所需的操作次数。

输入格式

输入包含一行：

$N$ $p_1$ $p_2$ ... $p_N$

输出格式

输出高桥君完成排序所需的操作次数。

样例 1

输入

5
3 5 1 2 4

输出

3

样例 2

输入

5
5 4 3 2 1

输出

4

样例 3

输入

10
2 10 5 7 3 6 4 9 8 1

输出

6

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $(p_1,p_2,\ldots,p_N)$ 是 $1$ 到 $N$ 的一个排列。

样例说明 1

高桥君最开始有排列 $(3,5,1,2,4)$，每次操作后，排列如下所示：

• 第 $1$，$2$ 项是高项，第 $3$，$4$，$5$ 项是低项，所以下一个排列是 $(1,2,4,3,5)$。
• 第 $1$，$2$，$3$，$5$ 项是高项，第 $4$ 项是低项，所以下一个排列是 $(3,1,2,4,5)$。
• 第 $1$，$4$，$5$ 项是高项，第 $2$，$3$ 项是低项，所以下一个排列是 $(1,2,3,4,5)$。

由 ChatGPT 5 翻译