配点 : $600$ 点

問題文

高橋君は、誕生日に長さ $N$ の数列をもらいました。$i(1 \leq i \leq N)$ 番目の要素は整数 $A_i$ です。どの $2$ つの要素も、互いに異なります。 高橋君はこの数列を単調増加になるように並べ替えたいです。 高橋君は超能力者なので、以下の $2$ つの操作が任意のタイミングでできます。

• 操作$1$: 数列の連続する $2$ つの要素を選び、その $2$ つの順番を反転する。
• 操作$2$: 数列の連続する $3$ つの要素を選び、その $3$ つの順番を反転する。

高橋君は操作$2$は好きですが、操作$1$は嫌いです。この $2$ 種類の操作を使って数列を単調増加になるように並び替えるときの、操作$1$の最小回数を求めてください。

制約

• $1 \leq N \leq 10^5$
• $0 \leq A_i \leq 10^9$
• $i \neq j$ ならば $A_i \neq A_j$
• 入力はすべて整数である。

入力

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

$N$

$A_1$

:

$A_N$

出力

操作$1$の最小回数を出力せよ。

4
2
4
3
1

1

以下の操作で、単調増加な数列にすることができます。

• まず、後ろの $3$ つの要素を反転する。数列は $2,1,3,4$ となる。
• 次に、前の $2$ つの要素を反転する。数列は $1,2,3,4$ となる。

この操作列において、連続する $2$ つの要素を入れ替える操作の回数は $1$ です。これより少ない回数で単調増加な数列は作れないので、$1$ を出力します。

5
10
8
5
3
2

0