题目描述

Farmer John wants to take a picture of his entire herd of N (1 <= N <= 100,000) cows conveniently numbered 1..N so he can show off to his friends.

On picture day, the cows run to form a single line in some arbitrary order with position i containing cow c_i (1 <= c_i <= N). Farmer John has his own ideas about how the cows should line up.

FJ thinks cow i may stand only to the left of cow i+1 (for all i, 1 <= i <= N-1) and that cow N may only stand to the left of Cow 1. Of course, no cow will stand to the left of the first (leftmost) cow in the line.

The cows are hungry for the promised post-photo dinner, so Farmer John wants to take the picture as quickly as possible. Cows are not great at following directions, so he will only choose a pair of adjacent cows and have them switch places once per minute. How quickly is Farmer John able to get them into some acceptable order?

Consider a set of 5 cows whose initial lineup looks like this:

Left Right

3 5 4 2 1

He can first swap the second pair of cows:

3 4 5 2 1

and then swap the rightmost pair:

3 4 5 1 2

to yield an acceptable lineup that required but two minutes of cow swapping.

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains the number of the i-th cow in line: c_i

输出格式

* Line 1: The minimum amount of time, in minutes, that it takes Farmer John to get the cows into some appropriate order.

题目大意

FJ 希望给他的 $N(1\leq N \leq 10^5)$ 只奶牛拍照片，这样他就可以向他的朋友炫耀他的奶牛。这 $N$ 只奶牛被标号为 $1,\cdots,N$。在照相的那一天，奶牛们排成了一排。其中第 $i$ 个位置上是标号为 $c_i(1\leq c_i\leq N)$ 的奶牛。对于奶牛的站位，FJ 有他自己的想法。

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

FJ 最小需要多少时间就能使奶牛站成一个可以接受的序列？

5 
3 
5 
4 
2 
1 

2