意気込んだ Farmer John は、いつもうまくいかないことに挑戦します。牛の群れ全体の写真を撮りたいのです。

写真をきれいにするため、牛を背の低い順に一列に並べたいと思っています。ところが並べた直後、いつもいたずらをする Bessie が列を出て、別の場所に入り直してしまいました！

Farmer John は 2 頭ずつの牛を交換して、群れ全体を正しい順序に戻したいと思っています。そのために必要な最小の交換回数を求めてください。

入力

入力の 1 行目には $N$（$2 \leq N \leq 100$）が与えられます。続く $N$ 行は Bessie が移動した後の列の牛の身長を表します。身長は $1 \ldots 1,000,000$ の範囲の整数です。同じ身長の牛がいてもかまいません。

出力

正しい順序にするために必要な最小の交換回数を出力してください。交換する牛は列の隣同士である必要はありません。

入出力例

入力 1

6
2
4
7
7
9
3

出力 1

3

注記

この例では Bessie は明らかに身長 3 の牛です。FJ は以下の 3 回の交換で整列できます：

2 4 7 7 9 3 - 元の列
2 4 7 7 3 9 - 最後の 2 頭を交換
2 4 3 7 7 9 - 最初の 7 と 3 を交換
2 3 4 7 7 9 - 4 と 3 を交換

問題作成者：Brian Dean