题目描述

$\red{Farmer John}$希望给他的$\red{N(1<=N<=100,000)}$只奶牛拍照片,这样他就可以向他的朋友炫耀他的奶牛.这$\red{N}$只奶牛被标号为$\red{1..N. }$在照相的那一天,奶牛们排成了一排.其中第$\red{i}$个位置上是标号为$\red{c_i(1<=c_i<=N)}$的奶牛.

对于奶牛的站位,$\red{Farmer John}$有他自己的想法. $\red{FJ}$是这么想的,标号为$\red{i(1<=i<=n-1)}$的奶牛只能站在标号为$\red{i+1}$的奶牛的左边,而标号为$\red{N}$的奶牛只能站在标号为$\red{1}$的奶牛的左边.当然,没有牛可以站在队列中最左边的奶牛的左边了.也就是说,最左边的奶牛编号是随意的. 这些奶牛都非常的饿,急切的希望吃到$\red{FJ}$承诺的在拍照后的大餐,所以$\red{FJ}$想眷的拍照.奶牛们的方向感非常的不好,所以$\red{FJ}$每一分钟只可以选择相邻的两只奶牛然后让他们交换位置.

$\red{FJ}$最小需要多少时间就能使奶牛站成一个可以接受的序列? 比方说一个有$\red{5}$只奶牛的例子,一开始序列是这样的: 左边 右边 $\red{3 5 4 2 1 }$第一分钟,$\red{FJ}$可以交换第二队奶牛$\red{(}$ 即$\red{5}$和$\red{4),}$交换后的队列: $\red{3 4 5 2 1 }$第二分钟,$\red{FJ}$交换最右边的一对,序列变成这样: $\red{3 4 5 1 2 }$这样,只用了$\red{2}$分钟,就是序列变为了一个$\red{FJ}$所希望的序列.

输入格式

第$\red{1}$行:一个单独的数$\red{N }$第$\red{2}$到$\red{n+1}$行:

第$\red{i+1}$行上的数表示站在第$\red{i}$的位置上的奶牛的编号$\red{(}$$\red{c_i).}$

输出格式

一个整数,表示是奶牛的序列变为一个合法的序列的最小花费时间.

样例

输入样例

5

3

5

4

2

1

输出样例

2