Description

有N个不同的数字，现在要求把这些数字升序排序，从左到右依次递增。只能做交换操作，但交换数字要有一定的代价，代价的大小就是交换的数字的和。给出N个数字，求将所有数字变为有序的最小代价。（数字均为正整数）

Input

多组输入。第1行：1个数N，表示数字的个数。（2
<=N <= 50000)。第2 - N + 1行：每行1个数，表示数字Wi。(1 <= Wi
<= 10^9)

Output

输出最小代价。

Sample Input

3
3
2
1

Sample Output

4

HINT

Source

NBU OJ