配点 : $2400$ 点

問題文

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

そこで、高橋君は $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)$ と並び替える。

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

制約

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

入力

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

$N$

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

出力

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

5
3 5 1 2 4

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$ 項目が低い項なので、次の順列は $(1,2,3,4,5)$ になる。

5
5 4 3 2 1

4

10
2 10 5 7 3 6 4 9 8 1

6