COWPIC - Cow Photographs

FJ希望给他的 N ( 1 ≤ N ≤ 100,000 ) 只奶牛拍照，这样他就可以向朋友们炫耀他的奶牛。这 N 只奶牛被标号为 1...N。 在照相的那一天，奶牛们排成了一排。其中第i个位置上是标号为 ci​​ ( 1 ≤ c​i​​ ≤ N ) 的奶牛。对于奶牛的站位，FJ有他自己的想法。 FJ是这么想的，标号为 i ( 1 ≤ i ≤ n−1 ) 的奶牛只能站在标号为 i+1 的奶牛的左边，而标号为 N 的奶牛只能站在标号为 1 的奶牛的左边。当然，没有牛可以站在队列中最左边的奶牛的左边了。（也就是说，最左边的奶牛编号是随意的。） 这些奶牛都非常饿，急切希望吃到FJ所承诺的拍照后的大餐，所以FJ想尽快的拍照。奶牛们的方向感非常不好，所以FJ每一分钟只可以选择相邻的两只奶牛然后让他们交换位置。FJ最少需要多少时间才能使奶牛站成一个可以接受的序列? 比方说一个有5只奶牛的例子，一开始的序列是这样的：3 5 4 2 1 第一分钟，FJ可以交换 5 号奶牛和 4 号奶牛，交换后队列变为：3 4 5 2 1 第二分钟，FJ可以交换 1 号奶牛和 2 号奶牛，之后序列就变成了这样：3 4 5 1 2 这样，只用了 2 分钟，序列就变为了FJ所希望的那样。

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.

\n5\n3\n5\n4\n2\n1\n\n

\n2\n