Farmer John は全 $N$ 頭、$1 \le N \le 100,000$、番号 $1..N$ の写真を撮り友人に自慢したいのです。

撮影当日、牛は走って任意順で一列になり、位置 $i$ は $c_{i}$、$1 \le c_{i} \le N$。彼には並び方の考えがあります。

FJ の考えでは、全 $i$、$1 \le i \le N-1$、で牛 $i$ は牛 $i+1$ の左にだけ立て、牛 $N$ は牛 $1$ の左にだけ立てます。もちろん先頭、最左の牛の左には誰もいません。

牛は約束された撮影後の夕食を待って空腹で、彼は急ぎます。指示が苦手なので毎分隣接二頭を一度だけ交換できます。許される順への最短時間は？

五頭の初期例：

     左           右
        3  5  4  2  1

まず二番目の組を交換：

        3  4  5  2 1

次に最も右の組：

        3  4  5  1  2

許される並びになり、交換は二分だけです。

入力

• 行 $1$：整数 $N$ 一つ。

• 行 $2..N+1$：行 $i+1$ に列の $i$ 番目の番号 $c_{i}$。

出力

• 行 $1$：適切な順にする最短時間、分単位。

入出力例

入力 1

5
3
5
4
2
1

出力 1

2

注記

問題作成者：Travis、2010