512001 - 牛排序

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

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

Input

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

Output

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

Examples

Input

3
2 3 1

Output

    7

Hint

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

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题