AT_agc014_f [AGC014F] Strange Sorting

[problemUrl]: https://atcoder.jp/contests/agc014/tasks/agc014_f 高橋君はソートをするのが大好きです。 そこで、高橋君は $ 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/A

N/A

### 制約 - $ 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) $ になる。