How to sort
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

坑坑作为一个ACMer,经常要对一组数字进行排序,在排序过程中,将两个数字交换位置的花销是这两个数字的和,慢慢的他想实现一种最低花销的排序方式,你们能帮助他吗?

输入描述:

输入包含多组测试数据。
每组测试输入包含一组数字包含的整数个数n以及n个整数mi(1<=n<1000,0<=mi<=10000)给定的整数互不重复。

输出描述:

对于每组测试数据,输出一个整数,给定整数按升序排序时所需花销的最小值。
示例1

输入

复制
4
3 1 5 4 

输出

复制
13