题目描述

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

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

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

输入格式

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

$N$ $A_1$ : $A_N$

输出格式

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

题目大意

给定一个序列 $a$，元素两两不同，可以使用两种操作。

1. 翻转相邻两个元素。
2. 翻转相邻三个元素。

问怎么操作使这个序列变成升序，并使操作一的次数最少。输出这个最少的次数。

4
2
4
3
1

1

5
10
8
5
3
2

0

提示

制約

• $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$ を出力します。