512001 - 牛排序

【题目描述】牛排序(cow)

农夫准备把他的N头牛按脾气的大小排序。他可以交换任意两头牛的位置,交换脾气值为X和Y的两头牛需耗时X+Y秒。 请计算把所有牛排好序的最短时间。

输入

第1行为一个数N(1≤N≤10000)。 随后N个数,顺序代表初始序列中每头牛的脾气值(1~100000之间的整数),其值各不相同。

输出

输出一个数,表示把所有牛排好序的最短时间。

样例

输入

3
2 3 1

输出

    7

提示

【样例说明】 队列里有三头牛,脾气分别为2,3,1,即2 3 1为初始序列。 交换脾气为3和1的牛(时间=1+3=4),序列为2 1 3。 交换脾气为1和2的牛(时间=2+1=3),序列为1 2 3。

时间限制 1 秒
内存限制 128 MB
统计
上一题 下一题