Farmer John 想拍全体 $N$ 头奶牛的照片，$1 \le N \le 100,000$，编号 $1..N$，向朋友炫耀。

拍照当天，奶牛跑成任意顺序的一列，位置 $i$ 是 $c_{i}$，$1 \le c_{i} \le N$。他对排列有自己的想法。

FJ 认为牛 $i$ 只能站在牛 $i+1$ 左边，对所有 $i$，$1 \le i \le N-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