输入描述 Input Description
输出描述 Output Description
样例输入 Sample Input
样例输出 Sample Output
数据范围及提示 Data Size & Hint
分析：一般涉及到这种位置交换的都与置换群有联系。
假设这里有一组数3 7 4 1 2 6 5
则排序后应该是1 2 3 4 5 6 7
与原数组比较 3 7 4 1 2 6 5
则这个两个数组就可以表示一个置换群，可以理解成元素的一一映射，“1”——>"3","2"——>"7"以此类推
这里介绍几个概念：
轮换：即映射的循环，如例子中1-3-4-1就是一个循环，用（1,3,4）表示
分解置换群：把置换群分解成若干个轮换
如例子分解出来就是：(1,3,4)(2,7,5)(6)
然后我们分析一下："1"想去"3"的位置，"3"想去"4“的位置，"4"想去"1"的位置；"2"想去"7"的位置，"7”想去"5“的位置，"5"想去"2”的位置，以此类推……可以发现不同的轮换互不影响，也就是说我们可以分开来单独处理，这同样也暗示我们了这题应该是贪心思路，因为这里局部最优就导致一定全局最优
下面考虑(1,3,4)：
我们的最终目标是把(1,3,4)通过若干交换变成(1)(3)(4)（每个元素都找准了自己位置），现在我们需要花费最少的代价交换它们
既然每个元素都想去它后面那个元素所在的元素位置（特殊的，最后一个想去第一个）。很自然而然的想到，拿其中一个数不断跟前面的数换（换到第一位接着换到最后一位），经过n-1次交换后每个元素都回到了自己应该的位置，即分解成了单元素轮换，而既然要它代价最小，肯定就是拿这个轮换中最小的数换。这样正确吗？
这里介绍一个引理：一个元素个数为n的轮换（n元环），分解成单元素轮换至少需要n-1交换
证明：
可以用数学归纳法证明：
a、一元环，不需要动. 0次。
b、二元环，直接交换即可.1次。
c、三元环，第一次交换，总是把环拆成一个二元与一个一元。然后再拆二元环. 1+1=2次.
d、四元环，第一次交换，有两种情况：拆成两个二环，或拆成一个三元环与一个一元环。
无论哪种情况. 1+1+1＝3. 1+2+0＝3.
e、假设拆k元环以内的环都只需要k-1次可以完成.现在来拆k+1元环。
显然，无论交换哪两个，总是把k元环拆成了两个环，根据假设，拆这两个环所需的次数
都是他们的元数-1.两个环的元数合起来为k+1,次数合起来就是k+1-2.再加上前面拆成
两个环需要一次，就是k+1-2+1=k次。
故命题得证。
恩到了这里我们发现我们的做法很好，保证了交换次数最少，同时代价也是最小的，但是这样真的可以吗！？
比如说，对100,101,102,103,104,99.如果按照上述方法来排序。代价为100+101+102+103+104+99*5次.实际上，为了避免每次移动99这样一个大数，如果外界还有一个很小的数，如1.我们可以第一步先把1跟99交换，然后再用1代替99完成那n-1次交换。完成后，再把1跟99换回去。这样代价为100+101+102+103+104+1*5 +(1+99)*2.显然代价要小
晕，这不禁让我们对这个做法有点怀疑，还有反例吗！？
不过仔细想想我们的思路是没有错的，反例存在的原因并不是各个轮换之间有影响而造成了，如果这样那我们的做法就肯定是错误的了。我们发现上述反例的最优解除了最开始和最末的交换不同之外，其他做法是一样的。于是我们意识到了问题所在，得不到最优解的原因是“交换的数字不够小”，有数字交换同一个轮换中的元素可以得到更小花费！！！！！！这个比轮换中最小的数还小的数在哪里！！！！！！！！！！！！！？？？？？？？？？？是整个置换群（即整个数组）中的最小的！！
于是我们想到了有两种可能：
1)取这个轮换中的最小数作上述操作
2）将整个置换群中的最小数m和这个轮换中的最小数m'交换;将m作上述操作；将m和m'换回来（为了对结果正确性无影响）
/*PS:为何是将轮换中最小数和置换群中最小数换，用第二小数换不行吗？
这里很好理解：假设换的不是最小数m'而是m''(m''>m')，则总代价就为m+m''+m*(n-1)+s-m+m+m''=(2m+m*(n-1)+s-m)+2m''>(2m+m*(n-1)+s-m)+2m'（即换最小数m'的代价），故应该是轮换中最小数和置换群中最小数换*/
算法总结：
①暴力分解置换群成若干轮换
②对于每个轮换单独处理：
1、求出这个轮换中最小值m‘和这个轮换中各个元素的总和s以及个数n，则上述第一种方案的代价为：Cost1=m'*(n-1)+s-m'
2、求出整个数组中最小值m，则上述第二种方案的代价为：Cost2=m+m'+m*(n-1)+s-m+m+m'
3、去Cost1和Cost2中的最小值作为此轮换处理结果，加入到最后结果中
注意：再回归到这个题目，注意到数字不是连续的，所以要离散处理