题目描述

高橋君はソートをするのが大好きです。

そこで、高橋君は $1$ から $N$ の順列 $(p_1,p_2,...,p_N)$ を用意し、この順列が $(1,2,...,N)$ になるまで以下の操作を繰り返すことにしました。

• まず、順列の各 $i$ 項目に対して、$1$ 項目から $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)$ と並び替える。

さて、高橋君がソートを完了するまでに何回の操作が必要か求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

高橋君がソートを完了するまでにかかる操作の回数を出力せよ。

题目大意

有一个长度为n的排列，现在你做了几次操作，陈述如下：

找出所有的i，满足：对于任意1≤j<i，aj<ai.

将这些ai移至序列末尾。没有移动的数之间的顺序不变，移动的数之间的顺序也不变。

可以证明，在有限次操作后，序列一定会变成1,2,3,...,n，你想知道最小的操作次数。

例如样例3：

10

2 10 5 7 3 6 4 9 8 1

6次操作后序列分别是：

5 7 3 6 4 9 8 1 2 10

3 6 4 8 1 2 5 7 9 10

4 1 2 5 7 3 6 8 9 10

1 2 3 6 4 5 7 8 9 10

4 5 1 2 3 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10

5
3 5 1 2 4

3

5
5 4 3 2 1

4

10
2 10 5 7 3 6 4 9 8 1

6

提示

制約

• $1\ ≦\ N\ ≦\ 2×10^5$
• $(p_1,p_2,...,p_N)$ は $1$ から $N$ の順列である。

Sample Explanation 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)$ になる。