题目描述

高桥喜欢排序。

他有一个由整数 $1$ 到 $N$ 组成的排列 $(p_1,p_2,...,p_N)$。现在，他将重复以下操作，直到排列变为 $(1,2,...,N)$：

• 首先，我们将定义排列中的 高元素 和 低元素。对于排列中的第 $i$ 个元素，如果从第 $1$ 个到第 $i$ 个（包括第 $i$ 个）之间的最大元素是第 $i$ 个元素自身，则第 $i$ 个元素是高元素，否则是低元素。
• 然后，让 $a_1,a_2,...,a_k$ 表示当前排列中的高元素的值，$b_1,b_2,...,b_{N-k}$ 表示当前排列中的低元素的值，它们在排列中出现的顺序保持不变。
• 最后，将排列重新排列为 $(b_1,b_2,...,b_{N-k},a_1,a_2,...,a_k)$。

排序需要多少次操作才能完成？

约束条件

• $1 ≤ N ≤ 2×10^5$
• $(p_1,p_2,...,p_N)$ 是由整数 $1$ 到 $N$ 组成的排列。

输入

输入从标准输入读取，格式如下：

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

输出

打印需要多少次操作才能完成排序。

示例输入 1

5
3 5 1 2 4

示例输出 1

3

初始排列是 $(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$ 和第 $5$ 个元素是低元素。排列变为：$(1,2,3,4,5)$。

示例输入 2

5
5 4 3 2 1

示例输出 2

4

示例输入 3

10
2 10 5 7 3 6 4 9 8 1

示例输出 3

6