AT_arc188_e [ARC188E] Gravity Sort

[problemUrl]: https://atcoder.jp/contests/arc188/tasks/arc188_e $ 1 $ から $ 2N $ までの番号がついた $ 2N $ 個のマスが、マス $ 1 $ を上として上下一列に並んでいます。各マスには $ 1 $ つずつボールが入っており、時刻 $ t=0 $ において、マス $ i $ にあるボールの重さは、 $ i=1,2,\ \ldots\ ,N $ では $ m_i $、 $ i=N+1,N+2,\ \ldots\ ,2N $ では $ 0 $ です。ただし、$ (m_1,\ m_2,\ \ldots\ ,\ m_N) $ は $ 1 $ から $ N $ までの整数を並び替えた数列です。 以下では、重さ $ i $ のボールを「ボール $ i $」、各ボールの入っているマスの番号を「ボールの位置」と呼ぶことにします。 時刻 $ t=0 $ 以降、時刻が $ 1 $ 進むごとに、重いボールが下に沈み、代わりに軽いボールが浮かび上がっていきます。 厳密には、以下の手順によって、時刻 $ t=t_0 $ における各ボールの位置から時刻 $ t=t_0+1 $ における各ボールの位置を定めます。 > - まず、$ i=N,N-1,\ldots\ ,2,1 $ の順に、以下の操作を行う。 > - ボール $ i $ の $ t=t_0+1 $ における位置がすでに定められている場合 > - **何もしない。** > - ボール $ i $ の $ t=t_0+1 $ における位置がまだ定められていない場合 > - $ t=t_0 $ にボール $ i $ の $ 1 $ つ下のマスが存在し、このマスに入っているボール（ボール $ j $ とする）がボール $ i $ より軽いとき、**ボール $ i $ と ボール $ j $ の $ t=t_0+1 $ における位置を、$ t=t_0 $ における両者の位置を交換したものとして定める。** > - 上記にあてはまらないとき、**ボール $ i $ の $ t=t_0+1 $ における位置を $ t=t_0 $ における位置と同じに定める。** > - 続いて、ボール $ 0 $ のうちこの時点で $ t=t_0+1 $ における位置が定められていないものについて、**それぞれ $ t=t_0+1 $ における位置を $ t=t_0 $ における位置と同じに定める。** このとき、ある時刻にボールが上から軽い順に並び、それ以降全てボールの位置が変化しなくなることが示せます。この状態に達する時刻を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ m_1 $ $ m_2 $ $ \ldots $ $ m_N $

答えを整数で出力せよ。

### 制約 - $ 1\leq\ N\leq\ 2\times\ 10^5 $ - $ 1\leq\ m_i\ \leq\ N $ - $ i\neq\ j $ のとき $ m_i\neq\ m_j $ - 入力される値はすべて整数である ### Sample Explanation 1 時刻 $ t=0 $ から $ t=1 $ にかけての動きは次のように定まります。（必要に応じて、下の図も参考にしてください。） > 1. ボール $ 3 $ について、$ t=1 $ における位置はまだ定められていない。$ 1 $ つ下のマスにはボール $ 1 $ があり、ボール $ 3 $ の方が重いため、$ t=1 $ には両者の位置を入れ替える。すなわち、ボール $ 3 $ の位置をマス $ 3 $、ボール $ 1 $ の位置をマス $ 2 $ に定める。 > 2. ボール $ 2 $ について、$ t=1 $ における位置はまだ定められていない。$ 1 $ つ下のマスにはボール $ 3 $ があり、これはボール $ 2 $ より重いため、ボール $ 2 $ の $ t=1 $ における位置を $ t=0 $ と同じに定める。 > 3. ボール $ 1 $ について、$ t=1 $ における位置は先のステップで既に定められている。 > 4. ボール $ 0 $ について、全て $ t=1 $ における位置はまだ定められていない。これらは全て $ t=1 $ での位置を $ t=0 $ と同じに定める。 続いて、時刻 $ t=1 $ から $ t=2 $ にかけての動きは次のように定まります。 > 1. ボール $ 3 $ について、$ t=2 $ における位置はまだ定められていない。$ 1 $ つ下のマスにはボール $ 0 $ があり、ボール $ 3 $ の方が重いため、$ t=2 $ には両者の位置を入れ替える。すなわち、ボール $ 3 $ の位置をマス $ 4 $、（ボール $ 3 $ の $ 1 $ つ下にあった）ボール $ 0 $ の位置をマス $ 3 $ に定める。 > 2. ボール $ 2 $ について、$ t=2 $ における位置はまだ定められていない。$ 1 $ つ下のマスにはボール $ 1 $ があり、ボール $ 2 $ の方が重いため、$ t=2 $ には両者の位置を入れ替える。すなわち、ボール $ 2 $ の位置をマス $ 2 $、ボール $ 1 $ の位置をマス $ 1 $ に定める。 > 3. ボール $ 1 $ について、$ t=2 $ における位置は先のステップで既に定められている。 > 4. ボール $ 0 $ について、$ t=1 $ にマス $ 4 $ にあったものの $ t=2 $ における位置は先のステップで既に定められている。それ以外について、$ t=2 $ での位置を $ t=1 $ と同じに定める。 この後も同様にボールの位置を定めていくと、時刻 $ t=6 $ に上から順にボール $ 0,0,0,1,2,3 $ が並び、以降ボールの位置が変化しないことが分かります。 !\[\](https://img.atcoder.jp/arc188/4e545d6825157293f80acafb7314f5d1.png)