序列排序

题目描述

小C有一个N个数的整数序列,这个序列的中的数两两不同。小C每次可以交换序列中的任意两个数,代价为这两个数之和。小C希望将整个序列升序排序,问小C需要的最小代价是多少?

输入输出格式

输入格式


第一行,一个整数N。 第二行,N个整数,表示小C的序列。

输出格式


一行,一个整数,表示小C需要的最小代价。

输入输出样例

输入样例 #1

6
8 4 5 3 2 7

输出样例 #1

34

说明

数据范围: 对于30%的数据,1<=N<=10; 对于全部的数据,1<=N<=100000,输入数据中的其他整数均为正整数且不超过 $10^9$。