Farmer John希望给他的N(1<=N<=100,000)只奶牛拍照片,这样他就可以向他的朋友炫耀他的奶牛.这N只奶牛被标号为1..N.

在照相的那一天,奶牛们排成了一排.其中第i个位置上是标号为c_i(1<=c_i<=N)的奶牛.对于奶牛的站位,Farmer John有他自己的想法.

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交换最右边的一对,序列变成这样:

　　　　3  4  5  1  2

这样,只用了2分钟,就是序列变为了一个FJ所希望的序列.

 

解题过程:刚写这道题时，没有看到题目中的"相邻"两个字，于是当成了置换来做，找使循环节最多的序列，一时间没想到什么办法，敲了个暴力交了一下，发现wa了，重新读题后发现了题目中有"相邻"两个字;

由于每次相邻的两个数字交换，每次交换一定会使逆序对数减小或增加1，可以证明最小的移动次数是逆序对数，然后就可以O(nlogn)，求一个序列的逆序对数；

但是最左端的数字不确定，考虑一下如果顺序变化序列对逆序对数有什么影响，可以让每个数加1，如果这个数是n，则变成1这样的顺序来变换序列；

这样很容易看出，其他数字+1对逆序对数没影响，只有n变成1这个变化会对逆序对数造成影响，然后就可以O(n)的复杂度顺序转移；

代码：

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include