AT_agc003_c [AGC003C] BBuBBBlesort!

[problemUrl]: https://atcoder.jp/contests/agc003/tasks/agc003_c 高橋君は、誕生日に長さ $ N $ の数列をもらいました。$ i(1\ ≦\ i\ ≦\ N) $ 番目の要素は整数 $ A_i $ です。どの $ 2 $ つの要素も、互いに異なります。 高橋君はこの数列を単調増加になるように並べ替えたいです。 高橋君は超能力者なので、以下の $ 2 $ つの操作が任意のタイミングでできます。 - 操作$ 1 $: 数列の連続する $ 2 $ つの要素を選び、その $ 2 $ つの順番を反転する。 - 操作$ 2 $: 数列の連続する $ 3 $ つの要素を選び、その $ 3 $ つの順番を反転する。 高橋君は操作$ 2 $は好きですが、操作$ 1 $は嫌いです。この $ 2 $ 種類の操作を使って数列を単調増加になるように並び替えるときの、操作$ 1 $の最小回数を求めてください。

N/A

N/A

### 制約 - $ 1\ ≦\ N\ ≦\ 10^5 $ - $ 0\ ≦\ A_i\ ≦\ 10^9 $ - $ i\ ≠\ j $ ならば $ A_i\ ≠\ A_j $ - 入力はすべて整数である。 ### Sample Explanation 1 以下の操作で、単調増加な数列にすることができます。 - まず、後ろの $ 3 $ つの要素を反転する。数列は $ 2,1,3,4 $ となる。 - 次に、前の $ 2 $ つの要素を反転する。数列は $ 1,2,3,4 $ となる。 この操作列において、連続する $ 2 $ つの要素を入れ替える操作の回数は $ 1 $ です。これより少ない回数で単調増加な数列は作れないので、$ 1 $ を出力します。